|

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
?
?
?
?