/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_MAX = 1000000;
int N;
struct Edge {
int to;
int len;
};
vector <Edge> adj[N_MAX + 2];
bool seen[N_MAX + 2];
Edge par[N_MAX + 2];
int depth[N_MAX + 2];
tuple <int, int, int> backEdge;
int curr[N_MAX + 2];
void dfs (int u) {
while (u != 0) {
seen[u] = true;
if (curr[u] < (int) adj[u].size()) {
Edge e = adj[u][curr[u]++];
if (seen[e.to] == false) {
par[e.to] = Edge{u, e.len};
depth[e.to] = depth[u] + 1;
u = e.to;
} else if (depth[e.to] > depth[u]) {
backEdge = make_tuple(u, e.to, e.len);
}
} else {
u = par[u].to;
}
}
}
bool root[N_MAX + 2];
ll maxAny[N_MAX + 2];
ll maxDown[N_MAX + 2];
queue <int> q;
vector <int> order;
void compute (int s) {
q.push(s);
seen[s] = true; depth[s] = 0;
while (q.empty() == false) {
int u = q.front(); q.pop();
order.push_back(u);
for (Edge e : adj[u]) {
if (seen[e.to] == false && root[e.to] == false) {
q.push(e.to);
seen[e.to] = true;
depth[e.to] = depth[u] + 1;
}
}
}
reverse(order.begin(), order.end());
for (int u : order) {
vector <ll> maxDowns;
for (Edge e : adj[u]) {
if (depth[u] < depth[e.to] && root[e.to] == false) {
maxAny[u] = max(maxAny[u], maxAny[e.to]);
maxDown[u] = max(maxDown[u], maxDown[e.to] + e.len);
maxDowns.push_back(maxDown[e.to] + e.len);
}
}
sort(maxDowns.begin(), maxDowns.end(), greater <ll> ());
if ((int) maxDowns.size() >= 2) {
maxAny[u] = max(maxAny[u], maxDowns[0] + maxDowns[1]);
}
maxAny[u] = max(maxAny[u], maxDown[u]);
}
order.clear();
}
int roots[N_MAX + 2];
int group[N_MAX + 2];
int cntRoots;
int cntGroups;
multiset <ll> s;
int main () {
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
cin >> N;
for (int u = 1; u <= N; u++) {
Edge e;
cin >> e.to >> e.len;
assert(u != e.to);
adj[u].push_back(Edge{e.to, e.len});
adj[e.to].push_back(Edge{u, e.len});
}
for (int u = 1; u <= N; u++) {
if (seen[u] == false) {
dfs(u);
int v1, v2, len; tie(v1, v2, len) = backEdge;
swap(v1, v2);
par[v2] = Edge{v1, len};
cntGroups++;
int v = v1;
while (v != v2) {
root[v] = true;
roots[++cntRoots] = v;
group[cntRoots] = cntGroups;
v = par[v].to;
}
root[v] = true;
roots[++cntRoots] = v;
group[cntRoots] = cntGroups;
}
}
fill(seen + 1, seen + N + 1, false);
for (int u = 1; u <= N; u++) {
if (root[u] == true) {
compute(u);
}
}
ll answer = 0;
for (int g = 1, i = 1; g <= cntGroups; g++) {
int j = i;
while (j < cntRoots && group[j + 1] == g) {
j++;
}
ll totalLen = 0;
ll maxLen = 0;
for (int k = i; k <= j; k++) {
int u = roots[k];
totalLen += par[u].len;
maxLen = max(maxLen, maxAny[u]);
}
ll len = 0;
for (int k = j; k > i; k--) {
int u = roots[k];
len += par[u].len;
s.insert(maxDown[u] + len);
}
ll lazy = 0;
for (int k = i, u = roots[i]; k <= j; k++) {
assert(s.empty() == false);
maxLen = max(maxLen, *s.rbegin() + lazy + maxDown[u]);
s.insert(maxDown[u] - lazy);
lazy += par[u].len;
u = par[u].to;
assert(s.find((maxDown[u] + totalLen) - lazy) != s.end());
s.erase(s.find((maxDown[u] + totalLen) - lazy));
}
answer += maxLen;
s.clear();
i = j + 1;
}
cout << answer << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
16 ms |
23764 KB |
Output is correct |
| 2 |
Correct |
17 ms |
23824 KB |
Output is correct |
| 3 |
Correct |
17 ms |
23808 KB |
Output is correct |
| 4 |
Correct |
14 ms |
23812 KB |
Output is correct |
| 5 |
Correct |
14 ms |
23764 KB |
Output is correct |
| 6 |
Correct |
16 ms |
23792 KB |
Output is correct |
| 7 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 8 |
Correct |
15 ms |
23796 KB |
Output is correct |
| 9 |
Correct |
12 ms |
23764 KB |
Output is correct |
| 10 |
Correct |
12 ms |
23800 KB |
Output is correct |
| 11 |
Correct |
13 ms |
23804 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
23932 KB |
Output is correct |
| 2 |
Correct |
14 ms |
23892 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
24020 KB |
Output is correct |
| 2 |
Correct |
17 ms |
24276 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
35 ms |
25192 KB |
Output is correct |
| 2 |
Correct |
60 ms |
27332 KB |
Output is correct |
| 3 |
Correct |
38 ms |
25504 KB |
Output is correct |
| 4 |
Correct |
24 ms |
24716 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
62 ms |
28740 KB |
Output is correct |
| 2 |
Correct |
102 ms |
32020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
180 ms |
39328 KB |
Output is correct |
| 2 |
Correct |
225 ms |
42736 KB |
Output is correct |
| 3 |
Correct |
324 ms |
50156 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
370 ms |
53636 KB |
Output is correct |
| 2 |
Correct |
424 ms |
70744 KB |
Output is correct |
| 3 |
Correct |
665 ms |
75332 KB |
Output is correct |
| 4 |
Correct |
760 ms |
90504 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
881 ms |
112116 KB |
Output is correct |
| 2 |
Correct |
1390 ms |
117880 KB |
Output is correct |
| 3 |
Correct |
693 ms |
82860 KB |
Output is correct |
| 4 |
Correct |
910 ms |
111732 KB |
Output is correct |
| 5 |
Correct |
895 ms |
112484 KB |
Output is correct |
| 6 |
Correct |
1676 ms |
93664 KB |
Output is correct |
| 7 |
Correct |
1235 ms |
127732 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
855 ms |
91840 KB |
Output is correct |
| 2 |
Correct |
792 ms |
91900 KB |
Output is correct |
| 3 |
Runtime error |
1118 ms |
131072 KB |
Execution killed with signal 9 |
| 4 |
Halted |
0 ms |
0 KB |
- |
