|

General

# Author Problem Lang Verdict Time Memory Sent Judged
89297365 Practice:
luogu_bot2
835F - 34 GNU C++11 Accepted 124 ms 33512 KB 2020-08-08 04:24:42 2020-08-08 04:24:42

→ Source
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+5;
const ll Inf=0x3f3f3f3f3f3f3f3f;
ll res,r[maxn],l[maxn],l0[maxn],r0[maxn],sum[maxn],ans1,ans2=Inf,f[maxn],cir[maxn];
struct Edge{
int to,next,w;
}e[maxn<<1];
void add(int u,int v,int w) {
e[++cnt].to=v;
e[cnt].w=w;
}
int fnd(int u,int fa=-1) {
if(vis[u]) return u;
vis[u]=-1;
int v=e[i].to;
if(v!=fa) {
res=fnd(v,u);
if(res) return cir[++tot]=u,sum[tot]=e[i].w,vis[u]=1,res==u?0:res;
}
}
return 0;
}
void dfs(int u,int fa=-1) {
int v=e[i].to;
if(vis[v]!=1&&v!=fa) {
dfs(v,u);
ans1=max(ans1,f[u]+f[v]+e[i].w);
f[u]=max(f[u],f[v]+e[i].w);
}
}
}
int main() {
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d%d%d",&x,&y,&z);
}
fnd(1);
sum[0]=0;
for(int i=1;i<=tot;i++) {
dfs(cir[i]);
sum[i]+=sum[i-1];
}
res=l[0]=l0[0]=-Inf;
for(int i=1;i<=tot;i++) {
l0[i]=max(l0[i-1],f[cir[i]]+sum[i]+res);
l[i]=max(l[i-1],f[cir[i]]+sum[i]);
res=max(res,f[cir[i]]-sum[i]);
}
res=r[tot+1],r0[tot+1]=-Inf;
for(int i=tot;i>=1;i--) {
r0[i]=max(r0[i+1],f[cir[i]]-sum[i]+res);
r[i]=max(r[i+1],f[cir[i]]+sum[tot]-sum[i]);
res=max(res,f[cir[i]]+sum[i]);
}
for(int i=1;i<=tot;i++) {
ans2=min(ans2,max(l[i-1]+r[i],max(l0[i-1],r0[i])));
}
printf("%lld\n",max(ans1,ans2));
return 0;
}

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