|

General

# Author Problem Lang Verdict Time Memory Sent Judged
87815327 Practice:
vjudge5
835F - 34 GNU C++11 Accepted 156 ms 32264 KB 2020-07-24 02:31:45 2020-07-24 02:31:45

→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200005,INF=1e18+5;
struct edge{int to,wei,nxt;}e[N<<1];
inline int fnd(int x,int fa=-1)
{
if(vis[x]) return x;else vis[x]=-1;
if(e[i].to!=fa)
{
res=fnd(e[i].to,x);
if(res) return cir[++cnt]=x,we[cnt]=e[i].wei,vis[x]=1,res==x?0:res;
}
return 0;
}
inline void dfs(int x,int fa=-1)
{
if(vis[e[i].to]!=1&&e[i].to!=fa)
dfs(e[i].to,x),ans1=max(ans1,f[x]+f[e[i].to]+e[i].wei),f[x]=max(f[x],f[e[i].to]+e[i].wei);
}
signed main()
{
scanf("%lld",&n),memset(vis,0,sizeof(vis)),memset(f,0,sizeof(f));
fnd(1),we[0]=0;for(int i=1;i<=cnt;i++) dfs(cir[i]),we[i]+=we[i-1];
res=l[0]=l0[0]=-INF;
for(int i=1;i<=cnt;i++) l0[i]=max(l0[i-1],f[cir[i]]+we[i]+res),l[i]=max(l[i-1],f[cir[i]]+we[i]),res=max(res,f[cir[i]]-we[i]);
res=r[cnt+1]=r0[cnt+1]=-INF;
for(int i=cnt;i>=1;i--) r0[i]=max(r0[i+1],f[cir[i]]-we[i]+res),r[i]=max(r[i+1],f[cir[i]]+we[cnt]-we[i]),res=max(res,f[cir[i]]+we[i]);
for(int i=1;i<=cnt;i++) ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
return printf("%lld\n",max(ans1,ans2)),0;
}

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