General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
93540660 Practice:
basic_string
835F - 34 GNU C++11 Accepted 171 ms 25560 KB 2020-09-23 10:59:59 2020-09-23 10:59:59
→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3,M=4e5+3;
#define ll long long
int he[N],to[M],len[M],ne[M],st[N],w[N],tp,b[N];
ll f[N],p[N],q[N],s[N],o[N],ans2;
int getc(int x,int y){
	if(b[x])return x;
	b[x]=2;
	for(int i=he[x],j,k;i;i=ne[i])if((j=to[i])!=y){
		k=getc(j,x);
		if(k)return st[++tp]=x,w[tp]=len[i],b[x]=1,k==x?0:k;
	}
	return 0;
}
void dfs(int x,int y){
	for(int i=he[x],j;i;i=ne[i])if((j=to[i])!=y&&b[j]!=1){
		dfs(j,x),ans2=max(ans2,f[x]+f[j]+len[i]),f[x]=max(f[x],f[j]+len[i]);
	}
}
int main(){
	int n,i,j,k,l,t=0;
	ll ans=1e18,u,v,o,q;
	scanf("%d",&n);
	for(i=0;i<n;++i){
		scanf("%d%d%d",&j,&k,&l);
		ne[++t]=he[j],to[t]=k,len[t]=l,he[j]=t;
		ne[++t]=he[k],to[t]=j,len[t]=l,he[k]=t;
	}
	getc(1,0);
	for(i=1;i<=tp;++i)dfs(st[i],0);
	for(i=1,u=v=0;i<tp;++i){
		s[i+1]=max(s[i],f[st[i]]+u+v),u=max(u,f[st[i]]-v),p[i+1]=max(p[i],f[st[i]]+v+w[1]),v+=w[i+1];
	}
	for(i=tp,u=v=o=q=0;i;--i){
		o=max(o,f[st[i]]+u+v),u=max(u,f[st[i]]-v),q=max(q,f[st[i]]+v),ans=min(ans,max(max(s[i],o),p[i]+q)),v+=w[i];
	}
	printf("%lld",max(ans,ans2));
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details