|

General

# Author Problem Lang Verdict Time Memory Sent Judged
93540660 Practice:
basic_string
835F - 34 GNU C++11 Accepted 171 ms 25560 KB 2020-09-23 10:59:59 2020-09-23 10:59:59

→ Source
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+3,M=4e5+3;
#define ll long long
int he[N],to[M],len[M],ne[M],st[N],w[N],tp,b[N];
ll f[N],p[N],q[N],s[N],o[N],ans2;
int getc(int x,int y){
if(b[x])return x;
b[x]=2;
for(int i=he[x],j,k;i;i=ne[i])if((j=to[i])!=y){
k=getc(j,x);
if(k)return st[++tp]=x,w[tp]=len[i],b[x]=1,k==x?0:k;
}
return 0;
}
void dfs(int x,int y){
for(int i=he[x],j;i;i=ne[i])if((j=to[i])!=y&&b[j]!=1){
dfs(j,x),ans2=max(ans2,f[x]+f[j]+len[i]),f[x]=max(f[x],f[j]+len[i]);
}
}
int main(){
int n,i,j,k,l,t=0;
ll ans=1e18,u,v,o,q;
scanf("%d",&n);
for(i=0;i<n;++i){
scanf("%d%d%d",&j,&k,&l);
ne[++t]=he[j],to[t]=k,len[t]=l,he[j]=t;
ne[++t]=he[k],to[t]=j,len[t]=l,he[k]=t;
}
getc(1,0);
for(i=1;i<=tp;++i)dfs(st[i],0);
for(i=1,u=v=0;i<tp;++i){
s[i+1]=max(s[i],f[st[i]]+u+v),u=max(u,f[st[i]]-v),p[i+1]=max(p[i],f[st[i]]+v+w[1]),v+=w[i+1];
}
for(i=tp,u=v=o=q=0;i;--i){
o=max(o,f[st[i]]+u+v),u=max(u,f[st[i]]-v),q=max(q,f[st[i]]+v),ans=min(ans,max(max(s[i],o),p[i]+q)),v+=w[i];
}
printf("%lld",max(ans,ans2));
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
?
?