General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
87816279 Practice:
luogu_bot4
835F - 34 GNU C++11 Accepted 155 ms 39768 KB 2020-07-24 03:22:19 2020-07-24 03:22:19
 
 
→ Source
#include <bits/stdc++.h>
#define int long long
#define ri register int
#define N 200005
using namespace std;
const int inf=1e18;
int n,cnt=0,tot=0,ans1=0,ans2=inf,h[N],d[N],v[N],w[N],l1[N],l2[N],r1[N],r2[N],cir[N];
struct edge {
    int u,v,w;
} e[N<<1];
inline void add(int u,int v,int w) {
    e[++tot]=(edge) {h[u],v,w},h[u]=tot;
}
int dfs1(int x,int f) {
    if (v[x]) return x;
    v[x]=-1;
    for (ri i=h[x]; i; i=e[i].u)
        if (e[i].v^f) {
            int t=dfs1(e[i].v,x);
            if (t) {
                cir[++cnt]=x,w[cnt]=e[i].w,v[x]=1;
                if (t^x) return t;
                return 0;
            }
        }
    return 0;
}
void dfs2(int x,int f) {
    for (ri i=h[x]; i; i=e[i].u)
        if (v[e[i].v]^1&&e[i].v^f)
            dfs2(e[i].v,x),ans1=max(ans1,d[x]+d[e[i].v]+e[i].w),d[x]=max(d[x],d[e[i].v]+e[i].w);
}
signed main() {
    scanf("%lld",&n);
    for (ri i=1,x,y,z; i<=n; i++) scanf("%lld%lld%lld",&x,&y,&z),add(x,y,z),add(y,x,z);
    dfs1(1,0),l1[0]=l2[0]=r1[cnt+1]=r2[cnt+1]=-inf;
    for (ri i=1; i<=cnt; i++) dfs2(cir[i],0),w[i]+=w[i-1];
    for (ri i=1,tmp=-inf; i<=cnt; i++)
        l1[i]=max(l1[i-1],d[cir[i]]+w[i]+tmp),l2[i]=max(l2[i-1],d[cir[i]]+w[i]),tmp=max(tmp,d[cir[i]]-w[i]);
    for (ri i=cnt,tmp=-inf; i; i--)
        r1[i]=max(r1[i+1],d[cir[i]]-w[i]+tmp),r2[i]=max(r2[i+1],d[cir[i]]-w[i]+w[cnt]),tmp=max(tmp,d[cir[i]]+w[i]);
    for (ri i=1; i<=cnt; i++) ans2=min(ans2,max(max(l1[i-1],r1[i]),l2[i-1]+r2[i]));
    printf("%lld",max(ans1,ans2));
    return 0;
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details