|

General

# Author Problem Lang Verdict Time Memory Sent Judged
97162591 Practice:
LHN200861
835F - 34 GNU C++11 Accepted 1122 ms 35976 KB 2020-10-30 14:18:58 2020-10-30 14:18:58

→ Source
#include<bits/stdc++.h>
using namespace std;
struct edge
{
long long to,weight,nxt;
}e[400005];
long long n,tot,cnt,ans,a1,a2=1e18;
void add(long long x,long long y,long long w)
{
}
long long find(long long x,long long fa=-1)
{
if(vis[x])return x;
else vis[x]=-1;
long long i;
if(e[i].to!=fa)
{
ans=find(e[i].to,x);
if(ans)
{
c[++cnt]=x;
w[cnt]=e[i].weight;
vis[x]=1;
return ans==x?0:ans;
}
}
return 0;
}
void dfs(long long x,long long fa=-1)
{
long long i;
if(vis[e[i].to]!=1&&e[i].to!=fa)
{
dfs(e[i].to,x);
a1=max(a1,f[x]+f[e[i].to]+e[i].weight);
f[x]=max(f[x],f[e[i].to]+e[i].weight);
}
}
int main()
{
long long i,x,y,v;
cin>>n;
memset(vis,0,sizeof(vis));
memset(f,0,sizeof(f));
for(i=1;i<=n;i++)
{
cin>>x>>y>>v;
}
find(1);
w[0]=0;
ans=l[0]=ll[0]=-1e18;
for(i=1;i<=cnt;i++)
{
dfs(c[i]);
w[i]+=w[i-1];
}
for(i=1;i<=cnt;i++)
{
ll[i]=max(ll[i-1],f[c[i]]+w[i]+ans);
l[i]=max(l[i-1],f[c[i]]+w[i]);
ans=max(ans,f[c[i]]-w[i]);
}
ans=r[cnt+1]=rr[cnt+1]=-1e18;
for(i=cnt;i>=1;i--)
{
rr[i]=max(rr[i+1],f[c[i]]-w[i]+ans);
r[i]=max(r[i+1],f[c[i]]+w[cnt]-w[i]);
ans=max(ans,f[c[i]]+w[i]);
}
for(i=1;i<=cnt;i++)
{
a2=min(a2,max(l[i-1]+r[i],max(ll[i-1],rr[i])));
}
cout<<max(a1,a2)<<endl;
return 0;
}

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