General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
98560576 Practice:
LHN200861
835F - 34 GNU C++11 Accepted 1107 ms 35980 KB 2020-11-16 14:42:42 2020-11-16 14:42:42
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
struct edge
{
	long long to,weight,nxt;
}e[400005];
long long n,tot,cnt,ans,a1,a2=1e18;
long long head[200005],c[200005],vis[200005],f[200005],w[200005],l[200005],ll[200005],r[200005],rr[200005];
void add(long long x,long long y,long long w)
{
	e[++tot]=(edge){y,w,head[x]};
	head[x]=tot;
}
long long find(long long x,long long fa=-1)
{
	if(vis[x])return x;
	else vis[x]=-1;
	long long i;
	for(i=head[x];i;i=e[i].nxt)
		if(e[i].to!=fa)
		{
			ans=find(e[i].to,x);
			if(ans)
			{
				c[++cnt]=x;
				w[cnt]=e[i].weight;
				vis[x]=1;
				return ans==x?0:ans;
			}
		}
	return 0;
}
void dfs(long long x,long long fa=-1)
{
	long long i;
	for(i=head[x];i;i=e[i].nxt)
		if(vis[e[i].to]!=1&&e[i].to!=fa)
		{
			dfs(e[i].to,x);
			a1=max(a1,f[x]+f[e[i].to]+e[i].weight);
			f[x]=max(f[x],f[e[i].to]+e[i].weight);
		}
}
int main()
{
	long long x,y,i,v;
	cin>>n;
	memset(vis,0,sizeof(vis));
	memset(f,0,sizeof(f));
	for(i=1;i<=n;i++)
	{
		cin>>x>>y>>v;
		add(x,y,v);
		add(y,x,v);
	}
	find(1);
	w[0]=0;
	ans=l[0]=ll[0]=-1e18;
	for(i=1;i<=cnt;i++)
	{
		dfs(c[i]);
		w[i]+=w[i-1];
	}
	for(i=1;i<=cnt;i++)
	{
		ll[i]=max(ll[i-1],f[c[i]]+w[i]+ans);
		l[i]=max(l[i-1],f[c[i]]+w[i]);
		ans=max(ans,f[c[i]]-w[i]);
	}
	ans=r[cnt+1]=rr[cnt+1]=-1e18;
	for(i=cnt;i>=1;i--)
	{
		rr[i]=max(rr[i+1],f[c[i]]-w[i]+ans);
		r[i]=max(r[i+1],f[c[i]]+w[cnt]-w[i]);
		ans=max(ans,f[c[i]]+w[i]);
	}
	for(i=1;i<=cnt;i++)
	{
		a2=min(a2,max(l[i-1]+r[i],max(ll[i-1],rr[i])));
	}
	cout<<max(a1,a2)<<endl;
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details