General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
29090284 Practice:
xiejun
835F - 34 GNU C++ Accepted 139 ms 31324 KB 2017-08-01 09:55:40 2017-08-01 09:55:40
→ Source
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
typedef long long ll;
const int N=200100;
int h[N],vis[N],fa[N],ok[N];
int a[N],n,tot,x,y,z,cnt,tm;
struct edge{int y,next,z;}g[N*2];
ll f[N],b[N],c[N];
ll q1[N],q2[N];
ll p1[N],p2[N];
ll ans,sum,mx;

void adp(int x,int y,int z){
	g[++tot].y=y;
	g[tot].next=h[x];
	g[tot].z=z;
	h[x]=tot;
}

void dfs(int x){
	vis[x]=++tm;
	for (int i=h[x];i;i=g[i].next)
	if (g[i].y!=fa[x]){
		if (!vis[g[i].y]){
			fa[g[i].y]=x;
			c[g[i].y]=g[i].z;
			dfs(g[i].y); 
		} else 
		if (vis[x]<vis[g[i].y]){
			int t=g[i].y;
			while (t!=x){
				ok[t]=1;
				b[++cnt]=c[t];
				a[cnt]=t;
				t=fa[t];
			}
			ok[x]=1;
			b[++cnt]=g[i].z;
			a[cnt]=x;
		}
	}
}

void gao(int x,int ff){
	for (int i=h[x];i;i=g[i].next)
	if (!ok[g[i].y] && g[i].y!=ff){
		gao(g[i].y,x);
		ans=max(ans,f[x]+f[g[i].y]+g[i].z);
		f[x]=max(f[x],f[g[i].y]+g[i].z);
	}
}

int main(){
//	freopen("a.in","r",stdin);
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		scanf("%d%d%d",&x,&y,&z);
		adp(x,y,z);adp(y,x,z);
	}
	dfs(1);
	for (int i=1;i<=n;i++)
		if (ok[i]) gao(i,0);
	
	for (int i=1;i<=cnt;i++){
		sum+=b[i-1];p1[i]=max(p1[i-1],f[a[i]]+sum);
		q1[i]=max(q1[i-1],f[a[i]]+sum+mx);
		mx=max(mx,f[a[i]]-sum);
	}
	ll tmp=b[cnt];sum=mx=b[cnt]=0;
	for (int i=cnt;i;i--){
		sum+=b[i];p2[i]=max(p2[i+1],f[a[i]]+sum);
		q2[i]=max(q2[i+1],f[a[i]]+sum+mx);
		mx=max(mx,f[a[i]]-sum);
	}
	ll mn=q1[cnt];
	for (int i=1;i<=cnt;i++)
		mn=min(mn,max(max(q1[i],q2[i+1]),p1[i]+p2[i+1]+tmp));
	ans=max(ans,mn);
	printf("%I64d\n",ans);
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details