General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
97181172 Practice:
jiangshanxyz
835F - 34 GNU C++11 Accepted 140 ms 50068 KB 2020-10-30 17:47:38 2020-10-30 17:47:38
→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,y,z,t,ts,s1,s2,res;
int head[400010],b[400010],c[400010],w[400010],f[400010],l[400010],ll[400010],r[400010],rr[400010];
struct edge
{
	int to,w,next;
}e[400010];
void add(int x,int y,int z)
{
	t++;
	e[t].to=y;
	e[t].w=z;
	e[t].next=head[x];
	head[x]=t;
}
int find(int x,int f=-1)
{
	if(b[x])return x;
	  else b[x]=-1;
	for(int i=head[x];i>0;i=e[i].next)
	if(e[i].to!=f) 
	{	
		res=find(e[i].to,x);
		if(res)
		{
			c[++ts]=x;
			w[ts]=e[i].w;
			b[x]=1; 
			if(res==x)return 0;
			  else return res;
		} 
	}
	return 0;
}
void dfs(int x,int fa=-1)
{
	for(int i=head[x];i;i=e[i].next)
	if(b[e[i].to]!=1&&e[i].to!=fa)
	{
		dfs(e[i].to,x);
		s1=max(s1,f[x]+f[e[i].to]+e[i].w);
		f[x]=max(f[x],f[e[i].to]+e[i].w);
	} 
}
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);
		add(y,x,z);
	}
	find(1);
	w[0]=0;
	for(int i=1;i<=ts;i++)dfs(c[i]),w[i]+=w[i-1];
	res=l[0]=ll[0]=-2e18;	
	for(int i=1;i<=ts;i++) 
	{
		ll[i]=max(ll[i-1],f[c[i]]+w[i]+res);
		l[i]=max(l[i-1],f[c[i]]+w[i]);
		res=max(res,f[c[i]]-w[i]);
	}
	res=r[ts+1]=rr[ts+1]=-2e18;	
	for(int i=ts;i>=1;i--) 
	{
		rr[i]=max(rr[i+1],f[c[i]]-w[i]+res);
		r[i]=max(r[i+1],f[c[i]]+w[ts]-w[i]);
		res=max(res,f[c[i]]+w[i]);
	}
	s2=2e18;
	for(int i=1;i<=ts;i++)s2=min(s2,max(l[i-1]+r[i],max(ll[i-1],rr[i])));
	cout<<max(s1,s2);
	return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details