General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
98568506 Practice:
jiangshanxyz
835F - 34 GNU C++11 Accepted 124 ms 50068 KB 2020-11-16 16:31:46 2020-11-16 16:31:46
 
 
→ Source
#include<bits/stdc++.h>
#define Max 2e18
#define Maxn 400010
#define int long long
using namespace std;
int n,x,y,z,t,ts,sum1,sum2,res;
int h[Maxn],b[Maxn],c[Maxn],w[Maxn],f[Maxn],l1[Maxn],l2[Maxn],r1[Maxn],r2[Maxn];
struct edge
{
	int to,w,next;
}e[Maxn];
void add(int x,int y,int z)
{
	t++;
	e[t].to=y;
	e[t].w=z;
	e[t].next=h[x];
	h[x]=t;
}
int find(int x,int f=-1)
{
	if(b[x])return x;
	  else b[x]=-1;
	for(int i=h[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=h[x];i;i=e[i].next)
	if(b[e[i].to]!=1&&e[i].to!=fa)
	{
		dfs(e[i].to,x);
		sum1=max(sum1,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=l1[0]=l2[0]=-Max;	
	for(int i=1;i<=ts;i++) 
	{
		l2[i]=max(l2[i-1],f[c[i]]+w[i]+res);
		l1[i]=max(l1[i-1],f[c[i]]+w[i]);
		res=max(res,f[c[i]]-w[i]);
	}
	res=r1[ts+1]=r2[ts+1]=-Max;
	for(int i=ts;i>=1;i--)
	{
		r2[i]=max(r2[i+1],f[c[i]]-w[i]+res);
		r1[i]=max(r1[i+1],f[c[i]]+w[ts]-w[i]);
		res=max(res,f[c[i]]+w[i]);
	}
	sum2=Max;
	for(int i=1;i<=ts;i++)sum2=min(sum2,max(l1[i-1]+r1[i],max(l2[i-1],r2[i])));
	cout<<max(sum1,sum2);
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details