|

General

# Author Problem Lang Verdict Time Memory Sent Judged
132112633 Practice:
bkifhr7
835F - 34 GNU C++14 Accepted 873 ms 19756 KB 2021-10-16 12:44:26 2021-10-16 12:44:26

→ Source
#include<bits/stdc++.h>
using namespace std;
#define N 200005
#define ll long long
int n,m,edge[N],use[N];
ll ans,ans2,F,val[N];
ll l[N],r[N],L[N],R[N],f[N];
bool vis[N];
inline void add(int x,int y,int k){
++tot;
to[tot]=y;
cost[tot]=k;
}
inline int dfs(int x,int fa){
if(vis[x]) return x;
vis[x]=1;
int u=to[i];
if(u==fa) continue;
F=dfs(u,x);
if(F){
++m,edge[m]=x,val[m]=cost[i],use[x]=2;
return F==x?0:F;
}
}
return 0;
}
inline void dfs2(int x,int fa){
int u=to[i];
if(use[u]==2||u==fa) continue;
dfs2(u,x);
ans=max(ans,f[x]+f[u]+cost[i]);
f[x]=max(f[x],f[u]+cost[i]);
}
}
signed main(){
int x,y,z;
cin>>n;
for(register int i=1;i<=n;++i){
cin>>x>>y>>z;
}
dfs(1,-1);
for(register int i=1;i<=m;++i)
dfs2(edge[i],0),val[i]+=val[i-1];

F=l[0]=L[0]=-1e18;
for(register int i=1;i<=m;++i){
L[i]=max(L[i-1],f[edge[i]]+val[i]+F);
l[i]=max(l[i-1],f[edge[i]]+val[i]);
F=max(F,f[edge[i]]-val[i]);
}
F=r[m+1]=R[m+1]=-1e18;
for(register int i=m;i>=1;--i){
R[i]=max(R[i+1],f[edge[i]]-val[i]+F);
r[i]=max(r[i+1],f[edge[i]]+val[m]-val[i]);
F=max(F,f[edge[i]]+val[i]);
}
ans2=1e18;
for(register int i=1;i<=m;++i)
ans2=min(ans2,max(l[i-1]+r[i],max(L[i-1],R[i])));
cout<<max(ans,ans2)<<endl;
return 0;
}



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