Submission #1257204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257204		fv3	Jobs (BOI24_jobs)	C++20	100 / 100	214 ms	75592 KiB

Main

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<vector<int>> adj;
vector<ll> x, profit, cost;
 
vector<priority_queue<pair<ll, int>>> vq;
 
void DFS(int index) {
    for (auto node : adj[index]) {
        DFS(node);
 
        if (profit[node] >= cost[node]) {
            vq[index].push({-cost[node], node});
        }
    }
    // Find minimum cost for positive profit
    cost[index] = max(0ll, -x[index]);
    profit[index] = max(0ll, x[index]);
 
    while (!vq[index].empty()) {
        int i;
        i = vq[index].top().second;
 
        if (cost[i] <= profit[index] || profit[index] < cost[index]) {
            vq[index].pop();
 
            if (cost[i] > profit[index] && profit[index] < cost[index]) {
                cost[index] += cost[i] - profit[index];
                profit[index] = profit[i];
            } else {
                profit[index] += profit[i] - cost[i];
            }
 
            // This is very scary
            if (vq[index].size() < vq[i].size()) {
                swap(vq[index], vq[i]);
            }
            while (!vq[i].empty()) {
                vq[index].push(vq[i].top());
                vq[i].pop();
            }
            vq[i] = {};
        } else {
            break;
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int N; ll S;
    cin >> N >> S;
 
    adj = vector<vector<int>>(N+1);
    x = vector<ll>(N+1);
    x[0] = S;
 
    for (int i = 1; i <= N; i++) {
        int p;
        cin >> x[i] >> p;
        adj[p].push_back(i);
    }
 
    cost = profit = vector<ll>(N+1);
    vq = vector<priority_queue<pair<ll, int>>>(N+1);
 
    DFS(0);
    cout << profit[0] - S << "\n";
 
    return 0;
}

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