|

General

# Author Problem Lang Verdict Time Memory Sent Judged
83340963 Practice:
vjudge5
835F - 34 GNU C++11 Accepted 124 ms 24568 KB 2020-06-11 04:03:46 2020-06-11 04:03:46

→ Source
#include<bits/stdc++.h>
#define maxn 200005
#define LL long long
using namespace std;
int n,fa[maxn],dep[maxn],cir[maxn],D[maxn],m;
LL ans,f[maxn],g1[maxn],g2[maxn],h1[maxn],h2[maxn];
//f:maxdep  g:double chain  h:single chain
bool onc[maxn];
int fir[maxn],nxt[maxn<<1],to[maxn<<1],w[maxn<<1],tot;
inline void bothline(int x,int y,int z){
nxt[++tot]=fir[x],fir[x]=tot,to[tot]=y,w[tot]=z;
nxt[++tot]=fir[y],fir[y]=tot,to[tot]=x,w[tot]=z;
}
void findcircle(int u,int ff){
dep[u]=dep[fa[u]=ff]+1;
for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff){
if(!dep[v]) findcircle(v,u);
else if(dep[v]<dep[u])
for(int j=u;;j=fa[j]) {onc[cir[++m]=j]=1;if(j==v) break;}
}
}
void dfs(int u,int ff){
for(int i=fir[u],v;i;i=nxt[i]) if((v=to[i])!=ff&&!onc[v]){
dfs(v,u),f[v]+=w[i];
ans=max(ans,f[u]+f[v]),f[u]=max(f[u],f[v]);
}
}
int main()
{
scanf("%d",&n);
for(int i=1,x,y,z;i<=n;i++) scanf("%d%d%d",&x,&y,&z),bothline(x,y,z);
findcircle(1,0);
for(int i=1;i<=m;i++) dfs(cir[i],0);
cir[m+1]=cir[1];
for(int k=1;k<=m;k++)
for(int i=fir[cir[k]];i;i=nxt[i]) if(to[i]==cir[k+1]) {D[k]=w[i];break;}
LL sum=0,mx=f[cir[1]]+D[1];
for(int i=2;i<=m;i++){
sum+=D[i-1];
h1[i]=max(h1[i-1],f[cir[i]]+sum);
g1[i]=max(g1[i-1],f[cir[i]]+mx);
mx=max(mx,f[cir[i]])+D[i];
}
sum=0,mx=f[cir[1]]+D[m];
for(int i=m;i>1;i--){
sum+=D[i];
h2[i]=max(h2[i+1],f[cir[i]]+sum);
g2[i]=max(g2[i+1],f[cir[i]]+mx);
mx=max(mx,f[cir[i]])+D[i-1];
}
LL Ans=1ll<<60;
for(int i=1;i<=m;i++) Ans=min(Ans,max(ans,max(max(g1[i],g2[i+1]),h1[i]+h2[i+1])));
printf("%lld\n",Ans);
}



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