|

General

# Author Problem Lang Verdict Time Memory Sent Judged
87392976 Practice:
vjudge5
835F - 34 GNU C++17 Accepted 156 ms 30232 KB 2020-07-20 05:26:40 2020-07-20 05:26:40

→ Source
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int e[N],edgenum,k=0;
ll s[N],dep[N],ans,sl[N],sr[N],l[N],r[N];
void addedge(int u, int v, int w){
vet[++edgenum]=v;
val[edgenum]=w;
}
void dfs(int u, int father){
fa[u]=father;
for(int i = head[u]; i; i = nxt[i]){
int v=vet[i],cost=val[i];
if(v==father) continue;
if(!fa[v]){
e[v]=cost;
dfs(v,u);
}else if(!k){
int x=u;a[0]=v;s[1]=cost;
while(x!=v){
a[++k]=x;s[k+1]=s[k]+e[x];x=fa[x];
}
a[++k]=v;
}
}
}
void dp(int u){
fa[u]=0;
for(int e = head[u]; e; e = nxt[e]){
int v=vet[e],cost=val[e];
if(fa[v]!=0){
dp(v);
ans=max(ans,dep[v]+cost+dep[u]);
dep[u]=max(dep[u],dep[v]+cost);
}
}
}
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 <= k; i++) fa[a[i]]=0;
for(int i = 1; i <= k; i++) dp(a[i]);
ll mx=-1e18;
l[0]=sl[0]=-1e18;
for(int i = 1; i <= k; i++){
sl[i]=max(sl[i-1],dep[a[i]]+s[i]+mx);
l[i]=max(l[i-1],dep[a[i]]+s[k]+s[i]);
mx=max(mx,dep[a[i]]-s[i]);
}
sr[k+1]=r[k+1]=mx=-1e18;
for(int i = k; i > 0; i--){
sr[i]=max(sr[i+1],dep[a[i]]-s[i]+mx);
r[i]=max(r[i+1],dep[a[i]]-s[i]);
mx=max(mx,dep[a[i]]+s[i]);
}
ll tmp=1e18;
for(int i = 1; i <= k; i++) tmp=min(tmp, max(l[i-1]+r[i], max(sl[i-1],sr[i])));
printf("%lld\n", max(ans,tmp));
return 0;
}


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