General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
103154931 Practice:
luogu_bot5
835F - 34 GNU C++11 Accepted 187 ms 35984 KB 2021-01-04 11:35:31 2021-01-04 11:35:31
→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+77,inf=1e18+5;
struct E
{
	int to,w,next;
}e[N<<1];
int n,cnt=0,tot=0,ans1=0,ans2=inf,yjy,ls[N],C[N],vis[N],f[N];
int W[N],l[N],lans[N],r[N],rans[N];
void add(int u,int v,int w) 
{
	e[++tot].to=v; e[tot].next=ls[u]; ls[u]=tot; e[tot].w=w;
}
int pre(int x,int fa=-1)
{
	if(vis[x]) return x;else vis[x]=-1;
	for(int i=ls[x]; i; i=e[i].next) 
	{
		int v=e[i].to;
		if(v==fa) continue;
		yjy=pre(v,x);
		if(yjy) return C[++cnt]=x,W[cnt]=e[i].w,vis[x]=1,yjy==x?0:yjy;
	}
	return 0;
}
void dfs(int x,int fa=-1)
{
	for(int i=ls[x]; i; i=e[i].next)
	{
		int v=e[i].to;
		if(vis[v]==1||v==fa) continue;
		dfs(v,x);
		ans1=max(ans1,f[x]+f[v]+e[i].w),f[x]=max(f[x],f[v]+e[i].w);
	}		
}
signed main()
{
	scanf("%lld",&n);
	for(int i=1,x,y,w; i<=n; i++) scanf("%lld%lld%lld",&x,&y,&w),add(x,y,w),add(y,x,w);
	pre(1),W[0]=0;
	for(int i=1; i<=cnt; i++) dfs(C[i]),W[i]+=W[i-1];
	yjy=l[0]=lans[0]=-inf;
	for(int i=1; i<=cnt; i++) 
		lans[i]=max(lans[i-1],f[C[i]]+W[i]+yjy),
		l[i]=max(l[i-1],f[C[i]]+W[i]),
		yjy=max(yjy,f[C[i]]-W[i]);
	yjy=r[cnt+1]=rans[cnt+1]=-inf;
	for(int i=cnt; i>=1; i--) 
		rans[i]=max(rans[i+1],f[C[i]]-W[i]+yjy),
		r[i]=max(r[i+1],f[C[i]]+W[cnt]-W[i]),
		yjy=max(yjy,f[C[i]]+W[i]);
	for(int i=1; i<=cnt; i++) 
		ans2=min(ans2,max(l[i-1]+r[i],max(lans[i-1],rans[i])));
	printf("%lld\n",max(ans1,ans2));
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details