General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
90286240 Practice:
vjudge5
835F - 34 GNU C++17 Accepted 171 ms 26592 KB 2020-08-18 10:32:52 2020-08-18 10:32:52
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=0x3f3f3f3f3f3f3f3f; 
const int N=2e5+5;
int n,u,v,w,head[N],vet[N*2],nxt[N*2],val[N*2],fa[N],a[N];
int edge[N],edgenum,k=0;
ll s[N],dep[N],ans,sl[N],sr[N],l[N],r[N];
void addedge(int u, int v, int w){
	vet[++edgenum]=v;
	val[edgenum]=w;
	nxt[edgenum]=head[u];
	head[u]=edgenum;
}
void dfs(int u, int father){
	fa[u]=father;
	for(int i = head[u]; i; i = nxt[i]){
		int v=vet[i],cost=val[i];
		if(v==father) continue;
		if(!fa[v]){
			edge[v]=cost;
			dfs(v,u);
		}else if(!k){
			int x=u;a[0]=v;s[1]=cost;
			while(x!=v){
				a[++k]=x;s[k+1]=s[k]+edge[x];x=fa[x];
			}
			a[++k]=v;
		}
	}
}
void find(int u){
	fa[u]=0;
	for(int e = head[u]; e; e = nxt[e]){
		int v=vet[e],cost=val[e];
		if(fa[v]!=0){
			find(v);
			ans=max(ans,dep[v]+cost+dep[u]);
			dep[u]=max(dep[u],dep[v]+cost);
		}
	}
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int u,v,w;
		scanf("%d%d%d", &u, &v, &w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	dfs(1,-1);
	for(int i = 1; i <= k; i++) fa[a[i]]=0;
	for(int i = 1; i <= k; i++) find(a[i]);
	ll mx=-INF;
	l[0]=sl[0]=-INF;
	for(int i = 1; i <= k; i++){
		sl[i]=max(sl[i-1],dep[a[i]]+s[i]+mx);
		l[i]=max(l[i-1],dep[a[i]]+s[k]+s[i]);
		mx=max(mx,dep[a[i]]-s[i]);
	}
	sr[k+1]=r[k+1]=mx=-INF;
	for(int i = k; i > 0; i--){
		sr[i]=max(sr[i+1],dep[a[i]]-s[i]+mx);
		r[i]=max(r[i+1],dep[a[i]]-s[i]);
		mx=max(mx,dep[a[i]]+s[i]);
	}
	ll tmp=INF;
	for(int i = 1; i <= k; i++) tmp=min(tmp, max(l[i-1]+r[i], max(sl[i-1],sr[i])));
	printf("%lld\n", max(ans,tmp));
	return 0;
} 
				  	    	 	  		  	
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details