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;
#define int long long
#define vec vector
const int MXN = 2'005;
vec<int> tree[MXN];
map<int, int> thr[MXN];
int x[MXN];
const int INF = 1e17;
void dfs(int u) {
map<int, int> ch_thrs;
for(int v : tree[u]) {
dfs(v);
for(auto [t, g] : thr[v]) {
ch_thrs[t] += g;
}
}
//int money = x[u];
int money = x[u];
int total_gain = x[u];
int extra = 0;
if(total_gain > 0) thr[u][extra] = total_gain;
for(auto [t, g] : ch_thrs) {
if(money >= t) {
money += g;
total_gain += g;
}
else {
if(total_gain > 0) total_gain = 0;
extra += t-money;
money = t;
total_gain += g;
money += g;
}
if(total_gain > 0) thr[u][extra] = total_gain;
}
// cerr << u << ": " ;
// for(auto [t, g] : thr[u]) {
// cerr << "(" << t << ", " << g << ")" << ' ';
// }
// cerr << '\n';
}
int32_t main() {
ios_base::sync_with_stdio(false);
int N, S;
cin >> N >> S;
N += 1;
x[0] = S;
for(int i = 1; i<N; i++) {
cin >> x[i];
int p;
cin >> p;
tree[p].push_back(i);
}
//cerr << "INPUT READ" << '\n';
dfs(0);
cout << thr[0][0]-S << '\n';
}
# | 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... |