Submission #1020687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020687		adaawf	Jobs (BOI24_jobs)	C++17	100 / 100	312 ms	88660 KiB

Main

#include <iostream>
#include <vector>
#include <set>
using namespace std;
vector<int> g[300005];
long long int a[300005];
multiset<pair<long long int, long long int>> s[300005];
void dfs(int x) {
    for (int w : g[x]) {
        dfs(w);
        if (s[x].size() < s[w].size()) {
            s[x].swap(s[w]);
        }
        for (auto v : s[w]) s[x].insert(v);
        s[w].clear();
    }
    if (a[x] > 0) {
        s[x].insert({0, a[x]});
    }
    else {
        long long int c = -a[x], ma = c, d = 0;
        while (!s[x].empty() && c != 0) {
            pair<long long int, long long int> p = *s[x].begin();
            long long int k = min(c, p.second);
            c -= k;
            p.second -= k;
            ma = max(ma, p.first + c + k);
            s[x].erase(s[x].begin());
            if (p.second != 0) s[x].insert(p);
        }
        while (!s[x].empty()) {
            pair<long long int, long long int> p = *s[x].begin();
            if (p.first >= ma) break;
            s[x].erase(s[x].begin());
            d += p.second;
        }
        s[x].insert({ma, d});
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    long long int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        a[i] = x;
        g[y].push_back(i);
    }
    dfs(0);
    long long int res = k;
    for (auto w : s[0]) {
        if (k >= w.first) {
            k += w.second;
        }
    }
    cout << k - res;
}

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