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;

int N,M,c[MAX],use[MAX],head[MAX];
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)
{
	E[i] = edge{y, z, head[x]};
	head[x] = 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);
		add(x, y, z, i*2); add(y, x, z, i*2-1);
	}
	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
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details