General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
42896070 Practice:
jangjie
835F - 34 GNU C++11 Accepted 187 ms 40476 KB 2018-09-15 18:34:22 2018-09-15 18:34:31
 
 
→ Source
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int N=2e5+7,inf=1e16;
struct edge {
	int t,nxt,w;
}e[N<<1];
int n,cnt,num,ans;
int head[N],fa[N],flg[N],a[N],S[N],dp[N],L[N],sL[N],R[N],sR[N];
void add(int u,int t,int w) {
	e[++cnt].t=t;e[cnt].w=w;e[cnt].nxt=head[u];head[u]=cnt; 
}
void dfs(int u,int F) {
	fa[u]=F;
	for (int i=head[u];i;i=e[i].nxt) {
		int t=e[i].t;
		if (t==F) continue;
		if (fa[t]) {
			if (num) continue;
			int x=u;
			while(1) {
				flg[x]=1;a[++num]=x;
				if (x==t) break;
				x=fa[x];
			}
			num=0;
		}
		else dfs(t,u);
		if (flg[u] && flg[t]) {
			S[++num]=S[num-1]+e[i].w;
		}
	}
}
void dfs1(int u,int F) {
	dp[u]=0;
	for (int i=head[u];i;i=e[i].nxt) {
		int t=e[i].t;
		if (flg[t] || t==F) continue;
		dfs1(t,u);
		ans=max(ans,dp[t]+dp[u]+e[i].w);
		dp[u]=max(dp[u],dp[t]+e[i].w);
	}
}
signed main() {
	scanf("%lld",&n);
	for (int i=1,u,v,w;i<=n;i++) {
		scanf("%lld%lld%lld",&u,&v,&w);
		add(u,v,w);add(v,u,w);
	}
	dfs(1,-1);
	for (int i=1;i<=num;i++) dfs1(a[i],-1);
	int mx=-inf;
	L[0]=sL[0]=-inf;
	for (int i=1;i<=num;i++) {
		sL[i]=max(sL[i-1],dp[a[i]]+S[i]+mx);
		L[i]=max(L[i-1],dp[a[i]]+S[i]+S[num]);
		mx=max(mx,dp[a[i]]-S[i]);
	}
	R[num+1]=sR[num+1]=mx=-inf;
	for (int i=num;i;i--) {
		sR[i]=max(sR[i+1],dp[a[i]]-S[i]+mx);
		R[i]=max(R[i+1],dp[a[i]]-S[i]);
		mx=max(mx,dp[a[i]]+S[i]);
	}
	int res=inf;
	for (int i=1;i<=num;i++) res=min(res,max(L[i-1]+R[i],max(sL[i-1],sR[i]))); 
	printf("%lld\n",max(res,ans));
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details