|

General

# Author Problem Lang Verdict Time Memory Sent Judged
135532622 Practice:
trsins
835F - 34 GNU C++14 Accepted 186 ms 30048 KB 2021-11-15 04:54:13 2021-11-15 04:54:14

→ Source
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=2e5+6;
const int inf=1e18;

struct edge{
int to,nxt,w;
}e[N<<1];

inline void addedge(int u,int v,int w){
e[++tot].to=v;
e[tot].w=w;
return;
}

inline int findring(int u,int fa){
if(vis[u])return u;
vis[u]=-1;
int v=e[i].to;
if(v==fa)continue;
int tmp=findring(v,u);
if(tmp){
g[++m]=u;
a[m]=e[i].w;
vis[u]=1;
if(tmp==u)return 0;
else return tmp;
}
}
return 0;
}

inline void dfs(int u,int fa){
int v=e[i].to;
if(v==fa||vis[v]==1)continue;
dfs(v,u);
len=max(len,f[u]+f[v]+e[i].w);
f[u]=max(f[u],f[v]+e[i].w);
}
return;
}

signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
}
findring(1,0);
for(int i=1;i<=m;i++)dfs(g[i],0);
for(int i=1;i<=m;i++)s[i]=s[i-1]+a[i];
now=f1[0]=f2[0]=-inf;
for(int i=1;i<=m;i++){
f1[i]=max(f1[i-1],f[g[i]]+s[i]+now);
f2[i]=max(f2[i-1],f[g[i]]+s[i]);
now=max(now,f[g[i]]-s[i]);
}
now=g1[m+1]=g2[m+1]=-inf;
for(int i=m;i>=1;i--){
g1[i]=max(g1[i+1],f[g[i]]-s[i]+now);
g2[i]=max(g2[i+1],f[g[i]]+s[m]-s[i]);
now=max(now,f[g[i]]+s[i]);
}
for(int i=1;i<=m;i++)ans=min(ans,max(max(f1[i-1],g1[i]),f2[i-1]+g2[i]));
//	cout<<ans<<" "<<len<<"*\n";
ans=max(ans,len);
printf("%lld",ans);
return 0;
}

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