Submission #1059060

#TimeUsernameProblemLanguageResultExecution timeMemory
1059060TonylJobs (BOI24_jobs)C++17
14 / 100
86 ms40940 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using vi = vector<int>; using pi = pair<ll,ll>; #define REP(i,n) for (int i = 0; i < n; i++) #define trav(a,x) for (auto& a : x) #define D(x) //cerr << #x << ": " << x << endl; #define all(x) (x).begin(), (x).end() const int MAX_N = 3*1e5+3; struct Info { ll off = 0; map<ll, ll> rew; void add(int r) { if (r == 0) return; if (r > 0) { rew[-off] += r; } else { r*=-1; //off += r; // go erasing ll stole = 0; ll bef = 0; if (rew.size()) { bef = rew.begin()->first; stole += rew.begin()->second; rew.erase(rew.begin()); } bef += r; while (rew.size() && rew.begin()->first < bef) { stole += rew.begin()->second; rew.erase(rew.begin()); } if (stole > 0) rew[bef-off] += stole; while (rew.size() && r) { if (rew.begin()->second > r) { rew.begin()->second -= r; r = 0; } else { r -= rew.begin()->second; rew.erase(rew.begin()); } } } } void merge(Info* other) { trav(o, other->rew) { ll re = o.first + other->off; rew[re-off] += o.second; } } }; int n; ll s; vi children[MAX_N]; int values[MAX_N]; bool done[MAX_N]; Info* dfs(int i) { done[i] = 1; if (children[i].size() == 0) { Info* info = new Info; info->add(values[i]); return info; } assert(children[i].size() == 1); Info* info = dfs(children[i][0]); info->add(values[i]); return info; } ll triv_dfs(int i) { done[i] = 1; ll tot = values[i]; trav(ch, children[i]) tot += triv_dfs(ch); return max(tot, 0ll); } signed main() { ios_base::sync_with_stdio(false); cin.tie(0); priority_queue<pi, vector<pi>, greater<pi>> q; cin >> n >> s; ll ss = s; REP(i,n) { int p; cin >> values[i] >> p; if (p == 0) continue; p--; children[p].push_back(i); } REP(i,n) { if (done[i]) continue; Info* info = dfs(i); trav(r, info->rew) { q.push({r.first+info->off, r.second}); } } while (q.size()) { auto r = q.top(); q.pop(); D(r.first); D(r.second); if (r.first <= s) s += r.second; //else break; } assert(s >= ss); cout << s - ss << endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...