General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
83342978 Practice:
vjudge3
835F - 34 GNU C++11 Accepted 171 ms 29100 KB 2020-06-11 05:16:22 2020-06-11 05:16:22
 
 
→ Source
#include <bits/stdc++.h>
#define pb push_back
#define to first
#define wt second
#define LL long long
using namespace std;
const int MAXN = 200005;
vector< pair<int,int> >e[MAXN];
int n, c[MAXN], m, dep[MAXN], fa[MAXN];
bool flg[MAXN];
void ser(int u, int ff) {
	dep[u] = dep[fa[u]=ff] + 1;
	for(auto v : e[u]) if(v.to != ff) {
		if(!dep[v.to]) ser(v.to, u);
		else if(dep[v.to] < dep[u])
			for(int j = u; ; j = fa[j]) { flg[c[++m] = j] = 1; if(j == v.to) break; }
	}
}
LL f[MAXN], ans, d[MAXN];
void dfs(int u, int ff) {
	for(auto v : e[u]) if(v.to != ff && !flg[v.to]) {
		dfs(v.to, u);
		ans = max(ans, f[u] + f[v.to] + v.wt);
		f[u] = max(f[u], f[v.to] + v.wt);
	}
}
LL lmx[MAXN], rmx[MAXN], lans[MAXN], rans[MAXN];
int main () {
	scanf("%d", &n);
	for(int i = 1, x, y, z; i <= n; ++i)
		scanf("%d%d%d", &x, &y, &z),
		e[x].pb(pair<int,int>(y, z)),
		e[y].pb(pair<int,int>(x, z));
	ser(1, 0); c[m+1] = c[1];
	for(int i = 1; i <= m; ++i) {
		dfs(c[i], 0);
		for(auto j : e[c[i]]) if(j.to == c[i+1]) { d[i] = j.wt; break; }
	}
	LL sum = 0, mx = f[c[1]] + d[1];
	for(int i = 2; i <= m; ++i) {
		sum += d[i-1];
		lmx[i] = max(lmx[i-1], f[c[i]] + sum);
		lans[i] = max(lans[i-1], f[c[i]] + mx);
		mx = max(mx, f[c[i]]) + d[i];
	}
	sum = 0, mx = f[c[1]] + d[m];
	for(int i = m; i > 1; --i) {
		sum += d[i];
		rmx[i] = max(rmx[i+1], f[c[i]] + sum);
		rans[i] = max(rans[i+1], f[c[i]] + mx);
		mx = max(mx, f[c[i]]) + d[i-1];
	}
	LL Ans = 1ll<<50;
	for(int i = 1; i <= m; ++i) Ans = min(Ans, max(max(lans[i], rans[i+1]), lmx[i] + rmx[i+1]));
	printf("%lld\n", max(ans, Ans));
}
		 		 	  		    			   	 	 	 	 	
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details