Submission #1218276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1218276		ani5h	Jobs (BOI24_jobs)	C++20	100 / 100	294 ms	61452 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

struct info {
    ll f, s;

    bool operator<(const info &o) const {
        if(f == o.f)
            return s < o.s;

        return f < o.f;
    }

    bool operator>(const info &o) const {
        if(f == o.f)
            return s > o.s;

        return f > o.f;
    }
};

using ds = priority_queue<info, vector<info>, greater<info>>;

void solve() {
    int n;
    ll s;
    cin >> n >> s;
        
    ll start = s;

    vector<ll> c(n + 1);
    vector<vector<int>> adj(n + 1);

    for(int i = 1, u; i <= n; i++) {
        cin >> c[i] >> u;
        
        adj[u].push_back(i);
        adj[i].push_back(u);
    }

    auto merge = [&](info &a, info &b) {
        ll net = a.s - a.f + b.s - b.f;
        a = {max(a.f, a.f - a.s + b.f), net + max(a.f, a.f - a.s + b.f)};
    };

    auto dfs = [&](auto &&self, int u, int p) -> ds {
        ds pq;

        for(auto &v : adj[u])
            if(v != p) {
                ds re = self(self, v, u);

                if(re.size() > pq.size())
                    swap(re, pq);

                while(re.size() > 0) {
                    pq.push(re.top());
                    re.pop();
                }
            }

        info us = {max(-c[u], 0ll), max(c[u], 0ll)};

        while(!pq.empty() && (us.s <= us.f || us.s >= pq.top().f)) {
            auto v = pq.top();
            merge(us, v);
            pq.pop();
        }

        if(us.f < us.s)
            pq.push(us);

        return pq;
    };

    ds v = dfs(dfs, 0, -1);

    while(!v.empty()) {
        info seg = v.top();
        v.pop();

        if(s < seg.f)
            break;

        s += seg.s - seg.f;
    }

    cout << s - start << '\n';
}

int main() {
	int t = 1;
//    cin >> t;
    while(t--)
        solve();
}

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