General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
109862719 Practice:
luogu_bot3
835F - 34 GNU C++11 Accepted 296 ms 139400 KB 2021-03-13 13:03:47 2021-03-13 13:03:47
 
 
→ Source
#include<bits/stdc++.h>
#define int long long
#define _to e[i].to
const int N=500050,inf=998244353353353;
using namespace std;

struct edge{int to,nx,w;}e[N<<2];
int hd[N],S;
map<int,int> a[N];
void add(int fr,int to,int w){
	e[++S]=(edge){to,hd[fr],w},hd[fr]=S; 
}

int w[N],n,x,y,z,stk[N],tp,v[N],cnt,s[N],fl,ic[N],d[N],ans,l[N],r[N],l0[N],r0[N],res,ans2=inf;

void fcr(int k,int fa){
	stk[++tp]=k,v[k]=1;
	for(int i=hd[k];i;i=e[i].nx)
		if(_to!=fa)
			if(v[_to]){
				if(!fl&&(fl=1)){
					while(stk[tp]!=_to)
						ic[s[++cnt]=stk[tp--]]=1;
					ic[s[++cnt]=stk[tp--]]=1;
				}
			}else fcr(_to,k); 
	--tp;
}
void dfs(int k,int fa){
	int mx=0,sc=0;
	for(int i=hd[k];i;i=e[i].nx)
		if(_to!=fa&&!ic[_to]){
			dfs(_to,k),d[k]=max(d[k],d[_to]+e[i].w);
			if(d[_to]+e[i].w>=mx)sc=mx,mx=d[_to]+e[i].w;
			else sc=max(sc,d[_to]+e[i].w);
		}
	ans=max(ans,sc+mx);
}

main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z),a[x][y]=a[y][x]=z;
	fcr(1,0);
	for(int i=1;i<=cnt;i++)dfs(s[i],0),w[i]=w[i-1]+a[s[i-1==0?cnt:i-1]][s[i]];
	res=l[0]=l0[0]=-inf;
	for(int i=1;i<=cnt;i++)
		l0[i]=max(l0[i-1],d[s[i]]+w[i]+res),l[i]=max(l[i-1],d[s[i]]+w[i]),res=max(res,d[s[i]]-w[i]);
	res=r[cnt+1]=r0[cnt+1]=-inf;
	for(int i=cnt;i;i--)
		r0[i]=max(r0[i+1],d[s[i]]-w[i]+res),r[i]=max(r[i+1],d[s[i]]+w[cnt]-w[i]),res=max(res,d[s[i]]+w[i]);
	for(int i=1;i<=cnt;i++)
		ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
	printf("%lld",max(ans,ans2));
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details