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>
#define int long long
using namespace std;
vector<vector<int>> sons;
int n,s;
vector<int> vals;
vector<int> parent;
vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>> needfuls;
set<pair<int,int>> set_conversion(priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> nv) {
set<pair<int,int>> S;
while (nv.size()) {
S.insert(nv.top()); nv.pop();
}
return S;
}
void dfs(int node) {
for (int j:sons[node]) {
dfs(j);
for (pair<int,int> k:set_conversion(needfuls[j])) {
needfuls[node].push(k);
}
}
int requirement,cursum;
cursum = vals[node];
if (vals[node]<0) {
requirement = -vals[node];
}
else {
requirement = 0;
}
while (needfuls[node].size() && cursum<0) {
pair<int,int> best = needfuls[node].top(); needfuls[node].pop();
requirement = max(requirement, best.first-cursum);
cursum+=best.second;
}
while (needfuls[node].size() && needfuls[node].top().first-cursum<=requirement) {
pair<int,int> best = needfuls[node].top(); needfuls[node].pop();
cursum+=best.second;
}
if (cursum>=0) {
needfuls[node].push({requirement,cursum});
}
}
signed main() {
#ifndef ONLINE_JUDGE
// for getting input from input.txt
freopen("input.txt", "r", stdin);
// for writing output to output.txt
freopen("output.txt", "w", stdout);
#endif
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#endif //fast IO
cin >> n >> s;
parent=vector<int>(n,-1);
sons=vector<vector<int>>(n);
vals=vector<int>(n);
needfuls=vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>>(n);
for (int i=0; i<n; i++) {
int val,prereq; cin >> val >> prereq; prereq--;
vals[i] = val;
if (prereq!=-1) {
sons[prereq].push_back(i);
}
}
int c = 1000;
int root = rand(); while (c--) root+=rand();
root%=n; root+=n; root%=n;
dfs(root);
int cursum = s;
for (pair<int,int> o:set_conversion(needfuls[root])) {
if (cursum<o.first) break;
cursum+=o.second;
}
int proooooooooofit = cursum-s;
cout << proooooooooofit << endl;
}
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |