#include <bits/stdc++.h>
#define maxn 300005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
int n, root;
int64_t c[maxn],s[maxn], T, mint[maxn];
ii edges[maxn];
int par[maxn], cl[maxn], dad[maxn], p[maxn];
vector<int> adj[maxn];
int find_set(int v) {
return par[v] == v ? v : par[v] = find_set(par[v]);
}
void union_set(int u, int v) {
u = find_set(u);
v = find_set(v);
if (u == v) return;
par[u] = v;
c[v] += c[u];
}
void efs(int u) {
for (int v : adj[u]) {
dad[v] = u;
efs(v);
}
}
void pfs(int u) {
if (cl[u]) {
s[u] = 0;
mint[u] = LLONG_MAX;
}
else {
mint[u] = min(mint[u], s[u] += c[u]);
}
for (int v : adj[u]) {
s[v] = s[u];
mint[v] = mint[u];
pfs(v);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> T;
int64_t old = T;
for (int i = 1; i <= n; i++) {
cin >> c[i] >> p[i];
edges[i] = ii{p[i], i};
}
iota(par, par+n+1, 0);
for (int i = 1; i <= n; i++) {
auto [u, v] = edges[i];
if (c[u] >= 0 && c[v] >= 0) union_set(u, v);
else if (c[u] < 0 && c[v] < 0) union_set(u, v);
else continue;
}
for (int i = 1; i <= n; i++) {
auto [u, v] = edges[i];
if ((c[u] >= 0 && c[v] >= 0) || (c[u] < 0 && c[v] < 0)) continue;
adj[find_set(u)].emplace_back(find_set(v));
}
root = find_set(0);
dad[root] = -1;
efs(root);
vector<int> debugHelper;
for (int i = 0; i <= n; i++) debugHelper.emplace_back(find_set(i));
sort(debugHelper.begin(), debugHelper.end());
debugHelper.erase(unique(debugHelper.begin(), debugHelper.end()), debugHelper.end());
for (int _ = 0; _ <= n; _++) {
s[root] = 0; mint[root] = LLONG_MAX;
pfs(root);
int p = -1;
int64_t mx = LLONG_MIN;
for (int i : debugHelper) {
if (!cl[i] && s[i] >= 0 && -mint[i] <= T && mx < s[i]) {
mx = s[i];
p = i;
}
}
if (p == -1) break;
T += s[p];
while (p != -1) {
cl[p] = 1;
p = dad[p];
}
}
cout << T - old;
}
/*
6 1
3 0
-3 1
-5 0
2 1
6 3
-4 5
6
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |