|

General

# Author Problem Lang Verdict Time Memory Sent Judged
137581619 Practice:
lijunhan
835F - 34 GNU C++14 Accepted 374 ms 53380 KB 2021-12-01 10:56:57 2021-12-01 10:56:57

→ Source
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int s=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
return s*w;
}
const int maxn = 400010;
int q[maxn],v[maxn],top,F[maxn],n,c[maxn<<1],T,ty[maxn];ll f[maxn],s[maxn<<1],aws;
struct E{int x,v;};
vector<E>g[maxn];void add(int x,int y,int z) {g[x].push_back((E){y,z}),g[y].push_back((E){x,z});}
int GF(int x) {return F[x]==x?x:F[x]=GF(F[x]);}
bool cir(int x,int fa) {
c[++top]=x;if(x==T) return 1;
for(E y:g[x]) if(y.x^fa&&cir(y.x,x)) return ty[x]=y.v,1;
return --top,0;
}
void dfs(int x,int fa) {
f[x]=0;
for(E y:g[x]) if(y.x^fa&&!v[y.x]) dfs(y.x,x),aws=max(aws,f[x]+f[y.x]+y.v),f[x]=max(f[x],f[y.x]+y.v);
}
ll fr[maxn],ed[maxn],fx[maxn],ex[maxn],ans=1e18;
signed main() {
for(int i=1;i<=n;i++) F[i]=i;
for(int i=1;i<=top;i++) v[c[i]]=1,s[i]=s[i-1]+ty[c[i-1]];
for(int i=1;i<=top;i++) dfs(c[i],0);
ll mx=-1e18;
for(int i=1;i<=top;i++) fr[i]=max(fr[i-1],f[c[i]]+s[i]),fx[i]=max(fx[i-1],f[c[i]]+s[i]+mx),mx=max(mx,f[c[i]]-s[i]);
mx=-1e18;
for(int i=top;i;i--) ed[i]=max(ed[i+1],f[c[i]]+s[top]-s[i]),ex[i]=max(ex[i+1],f[c[i]]-s[i]+mx),mx=max(mx,f[c[i]]+s[i]);
for(int i=1;i<top;i++) ans=min(ans,max(fx[i],max(ex[i+1],max(aws,fr[i]+ed[i+1]+ty[c[top]]))));
ans=min(ans,max(aws,fx[top]));
cout<<ans<<'\n';
return 0;
}

?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
Checker comment
?
Diagnostics
?
Click to see test details