Submission #1183695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183695		Cyanmond	Jobs (BOI24_jobs)	C++20	100 / 100	251 ms	64884 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ll2 = pair<ll, ll>;

int main() {
    int n;
    ll s;
    cin >> n >> s;

    n += 1;
    vector<ll> x(n);
    vector<vector<int>> g(n);
    x[0] = 0;
    for (int i = 1; i < n; ++i) {
        int p;
        cin >> x[i] >> p;
        g[p].push_back(i);
    }

    vector<priority_queue<ll2, vector<ll2>, greater<ll2>>> pqs(n);

    auto merge = [&](auto &pq1, auto &pq2) {
        if (int(pq1.size()) < int(pq2.size())) {
            swap(pq1, pq2);
        }
        while (not pq2.empty()) {
            pq1.push(pq2.top());
            pq2.pop();
        }
    };

    auto dfs = [&](auto &&self, int v) -> void {
        auto &pq = pqs[v];
        for (int t : g[v]) {
            self(self, t);
            merge(pq, pqs[t]);
        }

        if (x[v] > 0) {
            pq.push(make_pair(0ll, x[v]));
        } else if (not pq.empty()) {
            ll req = -x[v];
            ll prf = x[v];
            while (prf <= 0 and !pq.empty()) {
                auto [r, p] = pq.top();
                pq.pop();
                req = max(req, -prf + r);
                prf += p;
            }
            if (prf > 0) {
                while (!pq.empty() and pq.top().first <= req) {
                    prf += pq.top().second;
                    pq.pop();
                }
                pq.push(make_pair(req, prf));
            }
        }
    };

    dfs(dfs, 0);

    ll prf = 0;
    auto &pq = pqs[0];
    while (!pq.empty()) {
        auto [r, p] = pq.top();
        pq.pop();
        if (r <= prf + s) {
            prf += p;
        }
    }

    cout << prf << endl;
}

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31