#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif
const int N = (int) 1e6 + 100;
int g[N];
int deg[N + 1];
int p[N];
int l[N];
int nxt[N];
long long dist[N];
long long max_dist[N];
bool cycle[N];
bool was[N];
pair<int, long long> deq[N];
int order[N];
int dsu_get(int x) {
if (p[x] == x) {
return x;
} else {
return p[x] = dsu_get(p[x]);
}
}
bool dsu_unite(int x, int y) {
x = dsu_get(x);
y = dsu_get(y);
if (x == y) {
return false;
}
p[x] = y;
return true;
}
int x[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
iota(p, p + n, 0);
for (int i = 0; i < n; i++) {
int j;
cin >> j >> l[i];
j--;
deg[j + 1]++;
dsu_unite(i, j);
nxt[i] = j;
}
for (int i = 0; i < n; i++) {
deg[i + 1] += deg[i];
}
iota(g, g + n, 0);
sort(g, g + n, [&](int x, int y) {
if (nxt[x] == nxt[y]) {
return x < y;
}
return nxt[x] < nxt[y];
});
long long ans = 0;
for (int i = 0; i < n; i++) {
if (i != dsu_get(i)) {
continue;
}
int c = i;
while (!was[c]) {
was[c] = 1;
c = nxt[c];
}
int u = nxt[c];
cycle[c] = 1;
int sz = 1;
x[0] = c;
while (u != c) {
cycle[u] = 1;
x[sz++] = u;
u = nxt[u];
}
int sz2 = 0;
int beg = 0;
int end = 0;
for (int jj = 0; jj < sz; jj++) {
int j = x[jj];
deq[end++].first = j;
while (beg < end) {
int v = deq[beg++].first;
order[sz2++] = v;
for (int toid = deg[v]; toid < deg[v + 1]; toid++) {
int to = g[toid];
if (cycle[to]) {
continue;
}
dist[to] = dist[v] + l[to];
deq[end++].first = to;
}
}
}
long long t = 0;
for (int j = sz2 - 1; j >= 0; j--) {
int v = order[j];
max_dist[v] = max(max_dist[v], dist[v]);
if (cycle[v]) {
continue;
}
int to = nxt[v];
t = max(t, max_dist[to] + max_dist[v] - dist[to] * 2);
max_dist[to] = max(max_dist[to], max_dist[v]);
}
long long y = l[c];
beg = end = 0;
deq[end++] = make_pair(0, -max_dist[x[0]]);
for (int jj = 1; jj < sz * 2; jj++) {
int j = jj % sz;
if (x[deq[beg].first] == x[j]) {
beg++;
}
t = max(t, y + max_dist[x[j]] - deq[beg].second);
long long z = y - max_dist[x[j]];
while (beg < end && deq[end - 1].second >= z) {
end--;
}
y += l[x[j]];
deq[end++] = make_pair(j, z);
}
ans += t;
}
cout << ans << '\n';
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
332 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
460 KB |
Output is correct |
2 |
Correct |
2 ms |
588 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
972 KB |
Output is correct |
2 |
Correct |
14 ms |
2452 KB |
Output is correct |
3 |
Correct |
7 ms |
1484 KB |
Output is correct |
4 |
Correct |
3 ms |
844 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
19 ms |
3236 KB |
Output is correct |
2 |
Correct |
22 ms |
4476 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
49 ms |
11732 KB |
Output is correct |
2 |
Correct |
61 ms |
11328 KB |
Output is correct |
3 |
Correct |
69 ms |
15832 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
15104 KB |
Output is correct |
2 |
Correct |
111 ms |
29524 KB |
Output is correct |
3 |
Correct |
141 ms |
28768 KB |
Output is correct |
4 |
Correct |
148 ms |
40160 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
235 ms |
55024 KB |
Output is correct |
2 |
Correct |
353 ms |
54116 KB |
Output is correct |
3 |
Correct |
167 ms |
30148 KB |
Output is correct |
4 |
Correct |
217 ms |
48392 KB |
Output is correct |
5 |
Correct |
230 ms |
52252 KB |
Output is correct |
6 |
Correct |
625 ms |
49108 KB |
Output is correct |
7 |
Incorrect |
233 ms |
59292 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
246 ms |
67748 KB |
Output is correct |
2 |
Correct |
233 ms |
55028 KB |
Output is correct |
3 |
Incorrect |
324 ms |
65660 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |