|

General

# Author Problem Lang Verdict Time Memory Sent Judged
42896070 Practice:
jangjie
835F - 34 GNU C++11 Accepted 187 ms 40476 KB 2018-09-15 18:34:22 2018-09-15 18:34:31

→ Source
#include <cstdio>
#include <algorithm>
using namespace std;
#define int long long
const int N=2e5+7,inf=1e16;
struct edge {
int t,nxt,w;
}e[N<<1];
int n,cnt,num,ans;
void add(int u,int t,int w) {
}
void dfs(int u,int F) {
fa[u]=F;
int t=e[i].t;
if (t==F) continue;
if (fa[t]) {
if (num) continue;
int x=u;
while(1) {
flg[x]=1;a[++num]=x;
if (x==t) break;
x=fa[x];
}
num=0;
}
else dfs(t,u);
if (flg[u] && flg[t]) {
S[++num]=S[num-1]+e[i].w;
}
}
}
void dfs1(int u,int F) {
dp[u]=0;
int t=e[i].t;
if (flg[t] || t==F) continue;
dfs1(t,u);
ans=max(ans,dp[t]+dp[u]+e[i].w);
dp[u]=max(dp[u],dp[t]+e[i].w);
}
}
signed main() {
scanf("%lld",&n);
for (int i=1,u,v,w;i<=n;i++) {
scanf("%lld%lld%lld",&u,&v,&w);
}
dfs(1,-1);
for (int i=1;i<=num;i++) dfs1(a[i],-1);
int mx=-inf;
L[0]=sL[0]=-inf;
for (int i=1;i<=num;i++) {
sL[i]=max(sL[i-1],dp[a[i]]+S[i]+mx);
L[i]=max(L[i-1],dp[a[i]]+S[i]+S[num]);
mx=max(mx,dp[a[i]]-S[i]);
}
R[num+1]=sR[num+1]=mx=-inf;
for (int i=num;i;i--) {
sR[i]=max(sR[i+1],dp[a[i]]-S[i]+mx);
R[i]=max(R[i+1],dp[a[i]]-S[i]);
mx=max(mx,dp[a[i]]+S[i]);
}
int res=inf;
for (int i=1;i<=num;i++) res=min(res,max(L[i-1]+R[i],max(sL[i-1],sR[i])));
printf("%lld\n",max(res,ans));
}

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