|

General

# Author Problem Lang Verdict Time Memory Sent Judged
98568506 Practice:
jiangshanxyz
835F - 34 GNU C++11 Accepted 124 ms 50068 KB 2020-11-16 16:31:46 2020-11-16 16:31:46

→ Source
#include<bits/stdc++.h>
#define Max 2e18
#define Maxn 400010
#define int long long
using namespace std;
int n,x,y,z,t,ts,sum1,sum2,res;
int h[Maxn],b[Maxn],c[Maxn],w[Maxn],f[Maxn],l1[Maxn],l2[Maxn],r1[Maxn],r2[Maxn];
struct edge
{
int to,w,next;
}e[Maxn];
{
t++;
e[t].to=y;
e[t].w=z;
e[t].next=h[x];
h[x]=t;
}
int find(int x,int f=-1)
{
if(b[x])return x;
else b[x]=-1;
for(int i=h[x];i>0;i=e[i].next)
if(e[i].to!=f)
{
res=find(e[i].to,x);
if(res)
{
c[++ts]=x;
w[ts]=e[i].w;
b[x]=1;
if(res==x)return 0;
else return res;
}
}
return 0;
}
void dfs(int x,int fa=-1)
{
for(int i=h[x];i;i=e[i].next)
if(b[e[i].to]!=1&&e[i].to!=fa)
{
dfs(e[i].to,x);
sum1=max(sum1,f[x]+f[e[i].to]+e[i].w);
f[x]=max(f[x],f[e[i].to]+e[i].w);
}
}
signed main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&x,&y,&z);
}
find(1);
w[0]=0;
for(int i=1;i<=ts;i++)dfs(c[i]),w[i]+=w[i-1];
res=l1[0]=l2[0]=-Max;
for(int i=1;i<=ts;i++)
{
l2[i]=max(l2[i-1],f[c[i]]+w[i]+res);
l1[i]=max(l1[i-1],f[c[i]]+w[i]);
res=max(res,f[c[i]]-w[i]);
}
res=r1[ts+1]=r2[ts+1]=-Max;
for(int i=ts;i>=1;i--)
{
r2[i]=max(r2[i+1],f[c[i]]-w[i]+res);
r1[i]=max(r1[i+1],f[c[i]]+w[ts]-w[i]);
res=max(res,f[c[i]]+w[i]);
}
sum2=Max;
for(int i=1;i<=ts;i++)sum2=min(sum2,max(l1[i-1]+r1[i],max(l2[i-1],r2[i])));
cout<<max(sum1,sum2);
return 0;
}

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