|

General

# Author Problem Lang Verdict Time Memory Sent Judged
98660753 Practice:
QQH
835F - 34 GNU C++11 Accepted 109 ms 26344 KB 2020-11-17 11:07:13 2020-11-17 11:07:13

→ Source
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=200005;
ll ans1,ans2=1e18,s[N],f[N],l[N],l2[N],r[N],r2[N];
void add(int u,int v,int w){
edgenum++;
vet[edgenum]=v;
val[edgenum]=w;
}
int dfs(int u,int fa){
if(vis[u])return u;
vis[u]=1;
int v=vet[e];
if(v==fa)continue;
int tmp=dfs(v,u);
if(tmp){
p[++m]=u;s[m]=val[e];
vis[u]=2;
if(tmp==u)return 0;
else return tmp;
}
}
return 0;
}
void dfs2(int u,int fa){
int v=vet[e];
if(v==fa||vis[v]==2)continue;
dfs2(v,u);
ans1=max(ans1,f[u]+f[v]+val[e]);
f[u]=max(f[u],f[v]+val[e]);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
}
dfs(1,-1);
for(int i=1;i<=m;i++){
dfs2(p[i],0);
s[i]+=s[i-1];
}
ll res=-1e18;
l[0]=l2[0]=-1e18;
for(int i=1;i<=m;i++){
l[i]=max(l[i-1],f[p[i]]+s[i]);
l2[i]=max(l2[i-1],f[p[i]]+s[i]+res);
res=max(res,f[p[i]]-s[i]);
}
res=r[m+1]=r2[m+1]=-1e18;
for(int i=m;i>=1;i--){
r[i]=max(r[i+1],f[p[i]]+s[m]-s[i]);
r2[i]=max(r2[i+1],f[p[i]]-s[i]+res);
res=max(res,f[p[i]]+s[i]);
}
for(int i=1;i<=m;i++)
ans2=min(ans2,max(l[i-1]+r[i],max(l2[i-1],r2[i])));
printf("%lld",max(ans1,ans2));
return 0;
}

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