|

General

# Author Problem Lang Verdict Time Memory Sent Judged
60222269 Practice:
Ofnoname
835F - 34 GNU C++11 Accepted 124 ms 28896 KB 2019-09-07 17:03:54 2019-09-07 17:03:54
→ Source
// luogu-judger-enable-o2
#include <bits/stdc++.h>
#define MAX (200000 + 7)
#define long long long
using namespace std;

long ans1,ans2,FA,v[MAX],f[MAX],L[MAX],L0[MAX],R[MAX],R0[MAX];

struct edge{int y,z,nxt;} E[MAX<<1];
void add(int x, int y, int z, int i)
{
}

#define y E[p].y
#define z E[p].z
int DFS(int x, int fa)
{
if (use[x]) return x;

use[x] = 1;
for (int p = head[x]; p; p=E[p].nxt)
if (y != fa)
{
FA = DFS(y, x);
if (FA)
{
c[++M] = x; v[M] = z; use[x] = 2;
return FA==x ? 0 : FA;
}
}
return 0;
}

void DFS2(int x, int fa)
{
for (int p = head[x]; p; p=E[p].nxt)
if (use[y]!=2 && y!=fa)
{
DFS2(y, x);
ans1 = max(ans1, f[x] + f[y] + z);
f[x] = max(f[x], f[y] + z);
}
}
#undef y
#undef z

int main()
{
scanf("%d", &N);
for (int i = 1 ,x, y, z; i <= N; i++)
{
scanf("%d%d%d", &x, &y, &z);
}
DFS(1, -1);
for (int i = 1; i <= M; i++)
DFS2(c[i], 0), v[i] += v[i-1];

FA = L[0] = L0[0] = -1e18;
for (int i = 1; i <= M; i++)
{
L0[i] = max(L0[i-1], f[c[i]] + v[i] + FA);
L[i] = max(L[i-1], f[c[i]] + v[i]);
FA = max(FA, f[c[i]] - v[i]);
}
FA = R[M+1] = R0[M+1] = -1e18;
for (int i = M; i >= 1; i--)
{
R0[i] = max(R0[i+1], f[c[i]] - v[i] + FA);
R[i] = max(R[i+1], f[c[i]] + v[M]- v[i]);
FA = max(FA, f[c[i]] + v[i]);
}

ans2 = 1e18;
for (int i = 1; i <= M; i++)
ans2 = min(ans2, max(L[i-1]+R[i], max(L0[i-1], R0[i])));
printf("%lld\n", max(ans1, ans2));
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
?
Checker comment
?
Diagnostics
?
Click to see test details