This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
long long s;
cin >> s;
n += 1;
vector<int> x(n);
vector<int> p(n);
vector<vector<int>> g(n);
for (int i = 1; i < n; i++) {
cin >> x[i] >> p[i];
g[p[i]].push_back(i);
}
x[0] = 0;
p[0] = -1;
vector<multiset<pair<long long, long long>>> profit(n);
vector<long long> inc(n);
vector<int> where(n);
function<void(int)> Dfs = [&](int v) {
for (int u : g[v]) {
Dfs(u);
}
if (x[v] >= 0) {
where[v] = v;
profit[where[v]].emplace(0, x[v]);
for (int u : g[v]) {
if (profit[where[u]].size() > profit[where[v]].size()) {
swap(where[u], where[v]);
}
for (auto p : profit[where[u]]) {
profit[where[v]].insert(p);
}
}
} else {
where[v] = v;
for (int u : g[v]) {
if (profit[where[u]].size() > profit[where[v]].size()) {
swap(where[u], where[v]);
}
for (auto p : profit[where[u]]) {
profit[where[v]].insert(p);
}
}
long long dec = abs(x[v]);
long long mx = abs(x[v]);
long long bal = abs(x[v]);
while (dec > 0 && !profit[where[v]].empty()) {
mx = max(mx, bal + profit[where[v]].begin()->first);
long long t = min(dec, profit[where[v]].begin()->second);
dec -= t;
bal -= t;
pair<long long, long long> tmp = *profit[where[v]].begin();
profit[where[v]].erase(profit[where[v]].begin());
tmp.second -= t;
if (tmp.second > 0) {
profit[where[v]].insert(tmp);
}
}
long long sum = 0;
while (!profit[where[v]].empty() && profit[where[v]].begin()->first <= mx) {
sum += profit[where[v]].begin()->second;
profit[where[v]].erase(profit[where[v]].begin());
}
if (sum > 0) {
profit[where[v]].emplace(mx, sum);
}
}
};
Dfs(0);
long long start = s;
long long res = 0;
for (auto p : profit[where[0]]) {
if (s >= p.first) {
s += p.second;
}
}
cout << s - start << '\n';
return 0;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:77:13: warning: unused variable 'res' [-Wunused-variable]
77 | long long res = 0;
| ^~~
# | 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... |