|

General

# Author Problem Lang Verdict Time Memory Sent Judged
103154931 Practice:
luogu_bot5
835F - 34 GNU C++11 Accepted 187 ms 35984 KB 2021-01-04 11:35:31 2021-01-04 11:35:31
→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+77,inf=1e18+5;
struct E
{
int to,w,next;
}e[N<<1];
int n,cnt=0,tot=0,ans1=0,ans2=inf,yjy,ls[N],C[N],vis[N],f[N];
int W[N],l[N],lans[N],r[N],rans[N];
{
e[++tot].to=v; e[tot].next=ls[u]; ls[u]=tot; e[tot].w=w;
}
int pre(int x,int fa=-1)
{
if(vis[x]) return x;else vis[x]=-1;
for(int i=ls[x]; i; i=e[i].next)
{
int v=e[i].to;
if(v==fa) continue;
yjy=pre(v,x);
if(yjy) return C[++cnt]=x,W[cnt]=e[i].w,vis[x]=1,yjy==x?0:yjy;
}
return 0;
}
void dfs(int x,int fa=-1)
{
for(int i=ls[x]; i; i=e[i].next)
{
int v=e[i].to;
if(vis[v]==1||v==fa) continue;
dfs(v,x);
ans1=max(ans1,f[x]+f[v]+e[i].w),f[x]=max(f[x],f[v]+e[i].w);
}
}
signed main()
{
scanf("%lld",&n);
pre(1),W[0]=0;
for(int i=1; i<=cnt; i++) dfs(C[i]),W[i]+=W[i-1];
yjy=l[0]=lans[0]=-inf;
for(int i=1; i<=cnt; i++)
lans[i]=max(lans[i-1],f[C[i]]+W[i]+yjy),
l[i]=max(l[i-1],f[C[i]]+W[i]),
yjy=max(yjy,f[C[i]]-W[i]);
yjy=r[cnt+1]=rans[cnt+1]=-inf;
for(int i=cnt; i>=1; i--)
rans[i]=max(rans[i+1],f[C[i]]-W[i]+yjy),
r[i]=max(r[i+1],f[C[i]]+W[cnt]-W[i]),
yjy=max(yjy,f[C[i]]+W[i]);
for(int i=1; i<=cnt; i++)
ans2=min(ans2,max(l[i-1]+r[i],max(lans[i-1],rans[i])));
printf("%lld\n",max(ans1,ans2));
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
Checker comment
?
Diagnostics
?
Click to see test details