Основное
 
 
Отправитель Задача Язык Вердикт Время Память Отослано Протест.  
83340963 Дорешивание:
vjudge5
835F - 34 GNU C++11 Полное решение 124 мс 24568 КБ 2020-06-11 04:03:46 2020-06-11 04:03:46
→ Исходный код
#include<bits/stdc++.h>
#define maxn 200005
#define LL long long
using namespace std;
int n,fa[maxn],dep[maxn],cir[maxn],D[maxn],m;
LL ans,f[maxn],g1[maxn],g2[maxn],h1[maxn],h2[maxn];
//f:maxdep  g:double chain  h:single chain
bool onc[maxn];
int fir[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],tot;
inline void bothline(int x,int y,int z){
	nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,w[tot]=z;
	nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,w[tot]=z;
}
void findcircle(int u,int ff){
	dep[u]=dep[fa[u]=ff]+1;
	for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff){
		if(!dep[v]) findcircle(v,u);
		else if(dep[v]<dep[u])
			for(int j=u;;j=fa[j]) {onc[cir[++m]=j]=1;if(j==v) break;}
	}
}
void dfs(int u,int ff){
	for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff&&!onc[v]){
		dfs(v,u),f[v]+=w[i];
		ans=max(ans,f[u]+f[v]),f[u]=max(f[u],f[v]);
	}
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x,y,z;i<=n;i++) scanf("%d%d%d",&x,&y,&z),bothline(x,y,z);
	findcircle(1,0);
	for(int i=1;i<=m;i++) dfs(cir[i],0);
	cir[m+1]=cir[1];
	for(int k=1;k<=m;k++)
		for(int i=fir[cir[k]];i;i=nxt[i]) if(to[i]==cir[k+1]) {D[k]=w[i];break;}
	LL sum=0,mx=f[cir[1]]+D[1];
	for(int i=2;i<=m;i++){
		sum+=D[i-1];
		h1[i]=max(h1[i-1],f[cir[i]]+sum);
		g1[i]=max(g1[i-1],f[cir[i]]+mx);
		mx=max(mx,f[cir[i]])+D[i];
	}
	sum=0,mx=f[cir[1]]+D[m];
	for(int i=m;i>1;i--){
		sum+=D[i];
		h2[i]=max(h2[i+1],f[cir[i]]+sum);
		g2[i]=max(g2[i+1],f[cir[i]]+mx);
		mx=max(mx,f[cir[i]])+D[i-1];
	}
	LL Ans=1ll<<60;
	for(int i=1;i<=m;i++) Ans=min(Ans,max(ans,max(max(g1[i],g2[i+1]),h1[i]+h2[i+1])));
	printf("%lld\n",Ans);
}

  				  		   				  	 	 			 	  	
?
Время: ? ms, память: ? КБ
Вердикт: ?
Ввод
?
Вывод участника
?
Ответ жюри
?
Комментарий чекера
?
Диагностика
?
Показать детали тестирования