#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll
#define x first
#define y second
#define mp make_pair
#define mt make_tuple
#define all(x) x.begin(), x.end()
const int NODES = 4e6 + 10;
mt19937 rnd;
struct node {
int x, w, dy, sy, ls, rs;
} pool[NODES];
int ff = 1;
#define getter(f) int &f(int v) { assert(0 <= v && v < NODES); return pool[v].f; }
getter(x) getter(w) getter(dy) getter(sy) getter(ls) getter(rs)
int new_node(int nx, int ny) {
assert(ff < NODES);
int v = ff++;
x(v) = nx;
w(v) = (int)rnd();
dy(v) = ny;
sy(v) = ny;
ls(v) = rs(v) = 0;
return v;
}
int pull(int v) {
sy(v) = sy(ls(v)) + dy(v) + sy(rs(v));
return v;
}
void to_vector(int t, vector<pair<int, int>> &vec) {
if (!t) {
return;
}
to_vector(ls(t), vec);
vec.emplace_back(x(t), dy(t));
to_vector(rs(t), vec);
}
void print(int t) {
vector<pair<int, int>> v;
to_vector(t, v);
for (auto e : v) {
cout << "(" << e.x << "; " << e.y << ") ";
}
cout << endl;
}
pair<int, int> splitsum(int t, int s) {
if (!t) {
return {0, 0};
}
// print(t);
assert(0 <= s && s <= sy(t));
int lsum = sy(ls(t)), msum = dy(t);
if (lsum < s && lsum + msum > s) {
int lt = new_node(x(t), s - lsum), rt = new_node(x(t), msum - dy(lt));
ls(lt) = ls(t), rs(rt) = rs(t);
return {pull(lt), pull(rt)};
}
int l, r;
if (s <= lsum) {
tie(l, ls(t)) = splitsum(ls(t), s);
r = pull(t);
} else {
tie(rs(t), r) = splitsum(rs(t), s - lsum - msum);
l = pull(t);
}
assert(sy(l) == s);
return {l, r};
}
// (-inf, k], (k, +inf)
pair<int, int> split(int t, int k) {
if (!t) {
return {0, 0};
}
int l, r;
if (k < x(t)) {
tie(l, ls(t)) = split(ls(t), k);
r = pull(t);
} else {
tie(rs(t), r) = split(rs(t), k);
l = pull(t);
}
return {l, r};
}
int merge(int l, int r) {
if (!l) {
return r;
}
if (!r) {
return l;
}
if (w(l) < w(r)) {
rs(l) = merge(rs(l), r);
return pull(l);
} else {
ls(r) = merge(l, ls(r));
return pull(r);
}
}
int get_value(int t, int x) {
int l, r;
tie(l, r) = split(t, x);
int res = sy(l);
t = merge(l, r);
return res;
}
__attribute__((warn_unused_result))
int insert(int t, int nx, int ny) {
int l, m, r;
tie(l, m) = split(t, nx - 1);
tie(m, r) = split(m, nx);
// cout << "insert " << nx << " " << ny << endl;
// print(l);
// print(m);
// print(r);
// cout << "---" << endl;
m = new_node(nx, sy(m) + ny);
l = merge(l, m);
// print(l);
return merge(l, r);
}
__attribute__((warn_unused_result))
int uminpref(int t, int px) {
int checksum = sy(t);
int l, m, r;
tie(l, m) = split(t, px - 1);
tie(m, r) = split(m, px);
if (sy(m) <= 0) {
int p, q;
tie(p, q) = splitsum(l, sy(l) + sy(m));
t = merge(p, r);
assert(sy(t) == checksum);
return t;
} else {
return merge(merge(l, m), r);
}
}
__attribute__((warn_unused_result))
int add(int tv, int tu) {
if (!tv) {
return tu;
}
if (!tu) {
return tv;
}
tv = insert(tv, x(tu), dy(tu));
tv = add(tv, ls(tu));
tv = add(tv, rs(tu));
return tv;
}
const int N = 2e5 + 10;
int n, ia[N], ih[N], ic[N], dp[N];
vector<int> g[N];
bool used[N];
void dfs(int v) {
used[v] = true;
for (int u : g[v]) {
if (used[u]) {
continue;
}
dfs(u);
dp[u] = uminpref(dp[u], ih[u]);
// cout << "v = " << u + 1 << endl;
// print(dp[u]);
dp[v] = add(dp[v], dp[u]);
}
dp[v] = insert(dp[v], 0, ic[v]);
dp[v] = insert(dp[v], ih[v], -ic[v]);
dp[v] = insert(dp[v], ih[v] + 1, ic[v]);
}
signed main() {
#ifdef LC
assert(freopen("input.txt", "r", stdin));
#endif
ios::sync_with_stdio(0); cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> ia[i] >> ih[i] >> ic[i];
--ia[i];
g[ia[i]].push_back(i);
}
int answer = 0;
for (int i = 0; i < n; ++i) {
if (used[i]) {
continue;
}
int v = ia[i], u = ia[ia[i]];
while (v != u) {
v = ia[v];
u = ia[ia[u]];
}
dfs(v);
int t = dp[v];
u = ia[u];
// while (u != v) {
// dfs(u);
// t = add(t, dp[u]);
// u = ia[u];
// }
// cout << "v = " << v + 1 << endl;
// print(t);
t = uminpref(t, ih[v]);
// print(t);
// cout << get_value(t, 0) << endl;
vector<pair<int, int>> ve;
to_vector(t, ve);
int cur = (int)1e18, y = 0;
for (auto e : ve) {
y += e.y;
cur = min(cur, y);
}
answer += cur;
}
cout << answer << "\n";
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 5 |
Correct |
13 ms |
6984 KB |
Output is correct |
| 6 |
Correct |
11 ms |
6632 KB |
Output is correct |
| 7 |
Correct |
9 ms |
6476 KB |
Output is correct |
| 8 |
Correct |
14 ms |
7116 KB |
Output is correct |
| 9 |
Correct |
10 ms |
6604 KB |
Output is correct |
| 10 |
Correct |
9 ms |
6476 KB |
Output is correct |
| 11 |
Incorrect |
8 ms |
6136 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
14 ms |
7040 KB |
Output is correct |
| 2 |
Correct |
686 ms |
98632 KB |
Output is correct |
| 3 |
Correct |
451 ms |
80600 KB |
Output is correct |
| 4 |
Correct |
768 ms |
99208 KB |
Output is correct |
| 5 |
Correct |
459 ms |
80296 KB |
Output is correct |
| 6 |
Correct |
268 ms |
61380 KB |
Output is correct |
| 7 |
Incorrect |
236 ms |
49196 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 2 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 3 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
3 ms |
4940 KB |
Output is correct |
| 5 |
Correct |
13 ms |
6984 KB |
Output is correct |
| 6 |
Correct |
11 ms |
6632 KB |
Output is correct |
| 7 |
Correct |
9 ms |
6476 KB |
Output is correct |
| 8 |
Correct |
14 ms |
7116 KB |
Output is correct |
| 9 |
Correct |
10 ms |
6604 KB |
Output is correct |
| 10 |
Correct |
9 ms |
6476 KB |
Output is correct |
| 11 |
Incorrect |
8 ms |
6136 KB |
Output isn't correct |
| 12 |
Halted |
0 ms |
0 KB |
- |
