|

General

# Author Problem Lang Verdict Time Memory Sent Judged
132076784 Practice:
bkifhr9
835F - 34 GNU C++14 Accepted 218 ms 106428 KB 2021-10-16 04:02:20 2021-10-16 04:02:20

→ Source
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,e,cnt,ans,anss,ffa,p[1000005],beg[1000005],nex[1000005],to[1000005],w[1000005],a[1000005],dp[1000005],rt[1000005],l[1000005],r[1000005],ll[1000005],rr[1000005];
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
w[e]=z;
}
int dfs(int x,int fa){
if(p[x])return x;
p[x]=1;
for(int i=beg[x];i;i=nex[i])
if(to[i]!=fa){
ffa=dfs(to[i],x);
if(ffa){
rt[++cnt]=x;
a[cnt]=w[i];
p[x]=2;
return ffa==x?0:ffa;
}
}
return 0;
}
void dfss(int x,int fa){
for(int i=beg[x];i;i=nex[i])
if(p[to[i]]!=2&&to[i]!=fa){
dfss(to[i],x);
ans=max(ans,dp[x]+dp[to[i]]+w[i]);
dp[x]=max(dp[x],dp[to[i]]+w[i]);
}
}
signed main(){
scanf("%lld",&n);
int x,y,z;
for(int i=1;i<=n;i++)
dfs(1,0);
for(int i=1;i<=cnt;i++)
dfss(rt[i],0),a[i]+=a[i-1];
ffa=l[0]=ll[0]=-114514114514114514;
for(int i=1;i<=cnt;i++){
ll[i]=max(ll[i-1],dp[rt[i]]+a[i]+ffa);
l[i]=max(l[i-1],dp[rt[i]]+a[i]);
ffa=max(ffa,dp[rt[i]]-a[i]);
}
ffa=l[cnt+1]=ll[cnt+1]=-114514114514114514;
for(int i=cnt;i>=1;i--){
rr[i]=max(rr[i+1],dp[rt[i]]-a[i]+ffa);
r[i]=max(r[i+1],dp[rt[i]]+a[cnt]-a[i]);
ffa=max(ffa,dp[rt[i]]+a[i]);
}
anss=114514114514114514;
for (int i=1;i<=cnt;i++)
anss=min(anss,max(l[i-1]+r[i],max(ll[i-1],rr[i])));
printf("%lld\n",max(ans,anss));
return 0;
}



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