|

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);
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
?
?
?
?