Submission #995326

#TimeUsernameProblemLanguageResultExecution timeMemory
995326MilosMilutinovicJobs (BOI24_jobs)C++14
100 / 100
373 ms116304 KiB
#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 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...