General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
132656479 Practice:
CHK666
835F - 34 GNU C++17 (64) Accepted 405 ms 43432 KB 2021-10-22 02:55:24 2021-10-22 02:55:24
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 200005
struct edge{int v,next,w;}e[N<<1];
int n,cnt,ans1,ans2,rec,head[N],edgenum,cir[N],vis[N],f[N],val[N],l[N],l0[N],r[N],r0[N];
void add(int u,int v,int w){
	e[++edgenum]=edge{v,head[u],w};
	head[u]=edgenum;
}
int find(int u,int fa){
	if(vis[u])return u;
	else vis[u]=-1;
	for(int i=head[u],v;i;i=e[i].next)
		if((v=e[i].v)^fa){
			int rec=find(e[i].v,u);
			if(rec){
				cir[++cnt]=u;vis[u]=1;
				val[cnt]=e[i].w;
				return rec==u?0:rec;
			}
		}
	return 0;
}
void dfs(int u,int fa){
	for(int i=head[u],v;i;i=e[i].next)
		if(vis[v=e[i].v]!=1&&v!=fa){
			dfs(v,u);
			ans1=max(ans1,f[u]+f[v]+e[i].w);
			f[u]=max(f[u],f[v]+e[i].w);
		}
}
signed main(){
	ans2=1e18;scanf("%lld",&n);
	for(int i=1,u,v,w;i<=n;i++){
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	find(1,0);
	for(int i=1;i<=cnt;i++){
		dfs(cir[i],0);
		val[i]+=val[i-1];
	}
	rec=l[0]=l0[0]=-1e18;
	for(int i=1;i<=cnt;i++){
		l0[i]=max(l0[i-1],f[cir[i]]+val[i]+rec);
		l[i]=max(l[i-1],f[cir[i]]+val[i]);
		rec=max(rec,f[cir[i]]-val[i]);
	}
	rec=r[cnt+1]=r0[cnt+1]=-1e18;
	for(int i=cnt;i>=1;i--){
		r0[i]=max(r0[i+1],f[cir[i]]-val[i]+rec);
		r[i]=max(r[i+1],f[cir[i]]+val[cnt]-val[i]);
		rec=max(rec,f[cir[i]]+val[i]);
	}
	for(int i=1;i<=cnt;i++)ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
	printf("%lld\n",max(ans1,ans2));
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details