General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
132112633 Practice:
bkifhr7
835F - 34 GNU C++14 Accepted 873 ms 19756 KB 2021-10-16 12:44:26 2021-10-16 12:44:26
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
int tot=1,head[N],to[N<<1],nex[N<<1],cost[N<<1];
int n,m,edge[N],use[N];
ll ans,ans2,F,val[N];
ll l[N],r[N],L[N],R[N],f[N];
bool vis[N];
inline void add(int x,int y,int k){
	++tot;
	to[tot]=y;
	cost[tot]=k;
	nex[tot]=head[x];
	head[x]=tot;
}
inline int dfs(int x,int fa){
	if(vis[x]) return x;
	vis[x]=1;
	for(register int i=head[x];i;i=nex[i]){
		int u=to[i];
		if(u==fa) continue;
		F=dfs(u,x);
		if(F){
			++m,edge[m]=x,val[m]=cost[i],use[x]=2;
			return F==x?0:F;
		}
	}
	return 0;
}
inline void dfs2(int x,int fa){
	for(register int i=head[x];i;i=nex[i]){
		int u=to[i];
		if(use[u]==2||u==fa) continue;
		dfs2(u,x);
		ans=max(ans,f[x]+f[u]+cost[i]);
		f[x]=max(f[x],f[u]+cost[i]);
	}
}
signed main(){
	int x,y,z;
	cin>>n;
	for(register int i=1;i<=n;++i){
		cin>>x>>y>>z;
		add(x,y,z),add(y,x,z);
	}
	dfs(1,-1);
	for(register int i=1;i<=m;++i)
		dfs2(edge[i],0),val[i]+=val[i-1];

	F=l[0]=L[0]=-1e18;
	for(register int i=1;i<=m;++i){
		L[i]=max(L[i-1],f[edge[i]]+val[i]+F);
		l[i]=max(l[i-1],f[edge[i]]+val[i]);
		F=max(F,f[edge[i]]-val[i]);
	}
	F=r[m+1]=R[m+1]=-1e18;
	for(register int i=m;i>=1;--i){
		R[i]=max(R[i+1],f[edge[i]]-val[i]+F);
		r[i]=max(r[i+1],f[edge[i]]+val[m]-val[i]);
		F=max(F,f[edge[i]]+val[i]);
	}
	ans2=1e18;
	for(register int i=1;i<=m;++i)
		ans2=min(ans2,max(l[i-1]+r[i],max(L[i-1],R[i])));
	cout<<max(ans,ans2)<<endl;
	return 0;
}

	 	  	 		     	 	  	 	 	    			
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details