General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
137581619 Practice:
lijunhan
835F - 34 GNU C++14 Accepted 374 ms 53380 KB 2021-12-01 10:56:57 2021-12-01 10:56:57
 
 
→ Source
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int read() {
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
const int maxn = 400010;
int q[maxn],v[maxn],top,F[maxn],n,c[maxn<<1],T,ty[maxn];ll f[maxn],s[maxn<<1],aws;
struct E{int x,v;};
vector<E>g[maxn];void add(int x,int y,int z) {g[x].push_back((E){y,z}),g[y].push_back((E){x,z});}
int GF(int x) {return F[x]==x?x:F[x]=GF(F[x]);}
bool cir(int x,int fa) {
	c[++top]=x;if(x==T) return 1;
	for(E y:g[x]) if(y.x^fa&&cir(y.x,x)) return ty[x]=y.v,1;
	return --top,0;
}
void dfs(int x,int fa) {
	f[x]=0;
	for(E y:g[x]) if(y.x^fa&&!v[y.x]) dfs(y.x,x),aws=max(aws,f[x]+f[y.x]+y.v),f[x]=max(f[x],f[y.x]+y.v);
}
ll fr[maxn],ed[maxn],fx[maxn],ex[maxn],ans=1e18;
signed main() {
	n=read();
	for(int i=1;i<=n;i++) F[i]=i;
	for(int i=1,x,y;i<=n;i++) if(x=read(),y=read(),GF(x)^GF(y)) F[F[y]]=F[x],add(x,y,read());else T=y,cir(x,0),ty[y]=read();
	for(int i=1;i<=top;i++) v[c[i]]=1,s[i]=s[i-1]+ty[c[i-1]];
	for(int i=1;i<=top;i++) dfs(c[i],0);
	ll mx=-1e18;
	for(int i=1;i<=top;i++) fr[i]=max(fr[i-1],f[c[i]]+s[i]),fx[i]=max(fx[i-1],f[c[i]]+s[i]+mx),mx=max(mx,f[c[i]]-s[i]);
	mx=-1e18;
	for(int i=top;i;i--) ed[i]=max(ed[i+1],f[c[i]]+s[top]-s[i]),ex[i]=max(ex[i+1],f[c[i]]-s[i]+mx),mx=max(mx,f[c[i]]+s[i]);
	for(int i=1;i<top;i++) ans=min(ans,max(fx[i],max(ex[i+1],max(aws,fr[i]+ed[i+1]+ty[c[top]]))));
	ans=min(ans,max(aws,fx[top]));
	cout<<ans<<'\n';
	return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details