General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
135532622 Practice:
trsins
835F - 34 GNU C++14 Accepted 186 ms 30048 KB 2021-11-15 04:54:13 2021-11-15 04:54:14
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+6;
const int inf=1e18;

int n,m,head[N],tot,f[N],g[N],a[N],s[N],f1[N],g1[N],f2[N],g2[N],ans=inf,len,now,vis[N];

struct edge{
	int to,nxt,w;
}e[N<<1];

inline void addedge(int u,int v,int w){
	e[++tot].to=v;
	e[tot].nxt=head[u];
	head[u]=tot;
	e[tot].w=w;
	return;
}

inline int findring(int u,int fa){
	if(vis[u])return u;
	vis[u]=-1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa)continue;
		int tmp=findring(v,u);
		if(tmp){
			g[++m]=u;
			a[m]=e[i].w;
			vis[u]=1;
			if(tmp==u)return 0;
			else return tmp;
		}
	}
	return 0;
}

inline void dfs(int u,int fa){
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to;
		if(v==fa||vis[v]==1)continue;
		dfs(v,u);
		len=max(len,f[u]+f[v]+e[i].w);
		f[u]=max(f[u],f[v]+e[i].w);
	}
	return;
}

signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		addedge(u,v,w);
		addedge(v,u,w);
	}
	findring(1,0);
	for(int i=1;i<=m;i++)dfs(g[i],0);
	for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
	now=f1[0]=f2[0]=-inf;
	for(int i=1;i<=m;i++){
		f1[i]=max(f1[i-1],f[g[i]]+s[i]+now);
		f2[i]=max(f2[i-1],f[g[i]]+s[i]);
		now=max(now,f[g[i]]-s[i]);
	}
	now=g1[m+1]=g2[m+1]=-inf;
	for(int i=m;i>=1;i--){
		g1[i]=max(g1[i+1],f[g[i]]-s[i]+now);
		g2[i]=max(g2[i+1],f[g[i]]+s[m]-s[i]);
		now=max(now,f[g[i]]+s[i]);
	}
	for(int i=1;i<=m;i++)ans=min(ans,max(max(f1[i-1],g1[i]),f2[i-1]+g2[i]));
//	cout<<ans<<" "<<len<<"*\n";
	ans=max(ans,len);
	printf("%lld",ans);
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details