General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
83349563 Practice:
vjudge3
835F - 34 GNU C++17 Accepted 155 ms 27304 KB 2020-06-11 08:06:57 2020-06-11 08:06:57
 
 
→ Source
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
#define N 200005
int fir[N],to[2*N],nxt[2*N],cd[2*N],cnt;
void adde(int a,int b,int c)
{
	to[++cnt]=b;nxt[cnt]=fir[a];fir[a]=cnt;cd[cnt]=c;
	to[++cnt]=a;nxt[cnt]=fir[b];fir[b]=cnt;cd[cnt]=c;
}
#define LL long long
int cir[N],fa[N],dep[N];
bool vis[N];
void findcir(int u)
{
	dep[u]=dep[fa[u]]+1;
	int v,p;
	for(p=fir[u];p;p=nxt[p]){
		v=to[p];
		if(v==fa[u]) continue;
		if(!dep[v]){fa[v]=u;findcir(v);}
		else if(dep[v]<dep[u]){
			for(int j=u;;j=fa[j]){
				vis[j]=1;cir[++m]=j;
				if(j==v)break;
			}
		}
	}
}
LL hei[N],ans,D[N];
void dfs(int u,int ff)
{
	int v,p,w;
	for(p=fir[u];p;p=nxt[p]){
		v=to[p];w=cd[p];
		if(v!=ff&&!vis[v]){
			dfs(v,u);
			ans=max(hei[u]+hei[v]+w,ans);
			hei[u]=max(hei[u],hei[v]+w);
		}
	}
}
LL g1[N],g2[N],h1[N],h2[N];
int main()
{
	int n,i,u,v,w,p;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d%d%d",&u,&v,&w);
		adde(u,v,w);
	}
	findcir(1);
	for(i=1;i<=m;i++)dfs(cir[i],0);
	cir[m+1]=cir[1];
	for(i=1;i<=m;i++)
		for(p=fir[cir[i]];p;p=nxt[p])
			if(to[p]==cir[i+1]){D[i]=cd[p];break;}
	LL sum=0,mx=hei[cir[1]]+D[1];
	for(i=2;i<=m;i++){
		sum+=D[i-1];
		h1[i]=max(h1[i-1],hei[cir[i]]+sum);
		g1[i]=max(g1[i-1],hei[cir[i]]+mx);
		mx=max(mx,hei[cir[i]])+D[i];
	}
	sum=0;mx=hei[cir[1]]+D[m];
	for(i=m;i>1;i--){
		sum+=D[i];
		h2[i]=max(h2[i+1],hei[cir[i]]+sum);
		g2[i]=max(g2[i+1],hei[cir[i]]+mx);
		mx=max(mx,hei[cir[i]])+D[i-1];
	}
	LL ret=1ll<<60;
	for(i=1;i<=m;i++)
		ret=min(ret,max(h1[i]+h2[i+1],max(g1[i],g2[i+1])));
	printf("%lld",max(ans,ret));
}
 	 	 	 						 			 	 	 	 	  	  	
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details