Submission #1269471

#	Time	Username	Problem	Language	Result	Execution time	Memory
1269471		skibidigodv9	Jobs (BOI24_jobs)	C++20	100 / 100	253 ms	110812 KiB

Main

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

long long INF = 2e18;

struct hyperDSU {
    //dsu also contains pq
    vector<int> par;
    vector< priority_queue< pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> > PQ;
    void init(int n) {
        par.resize(n); PQ.resize(n);
        while (n--) par[n] = n;
        return;
    }
    
    int find(int u) {
        if (par[u] == u) return u;
        par[u] = find(par[u]);
        return par[u];
    }
    
    void pushToPQ(pair<long long, int>& x, int u) {
        u = find(u);
        PQ[u].push(x);
        return;
    }
    
    pair<long long, int> getPQTop(int u) {
        u = find(u);
        if (PQ[u].size() == 0) return {INF, 0};
        return PQ[u].top();
    }
    
    void clearPQTop(int u) {
        u = find(u);
        if (PQ[u].size() == 0) return;
        PQ[u].pop();
        return;
    }
    
    bool join(int u, int v) {
        u = find(u); v = find(v);
        if (u == v) return false;
        if (PQ[u].size() < PQ[v].size()) swap(u,v);
        while (PQ[v].size()) {
            PQ[u].push(PQ[v].top()); PQ[v].pop();
        }
        par[v] = u;
        return true;
    }
};

hyperDSU D;
vector<int> par;
vector<long long> A;
vector<pair<long long, long long>> dp; //dp ={min S required, advantage gain}
vector<vector<int>> E;

void dfs(int u) {
    for (auto v: E[u]) {
        dfs(v);
    }
    
    if (E[u].size() == 0) {
        //cout << "huh " << u << "\n";
        if (A[u] < 0) dp[u] = {INF, 0};
        else dp[u] = {0, A[u]};
    } else if (u != 0) {
        for (auto v: E[u]) {
            pair<long long, int> toAdd = {dp[v].first, v};
            D.pushToPQ(toAdd, u);
        }
        long long curS = A[u], Av = 0, P = A[u]; //P = profit
        if (curS < 0) {Av -= curS; curS = 0;}
        while (P < 0) {
            pair<long long, int> w = D.getPQTop(u);
            if (w.first == INF) break;
            
            D.clearPQTop(u);
            
            //if it's too low to get the advantage, supply more
            if (curS < w.first) {
                Av += w.first-curS;
                curS = w.first;
            }
            
            //apply the advantage
            curS += dp[w.second].second;
            P += dp[w.second].second;
            
            //merge u's PQ with the added PQ
            D.join(u, w.second);
        }
        if (P < 0) dp[u] = {INF, 0};
        else dp[u] = {Av, P};
    } else {
        //final result calculation
        for (auto v: E[u]) {
            pair<long long, int> toAdd = {dp[v].first, v};
            D.pushToPQ(toAdd, u);
        }
        long long curS = A[u];
        while (true) {
            pair<long long, int> w = D.getPQTop(u);
            if (curS < w.first) break;
            
            D.clearPQTop(u);
            
            //apply the advantage
            curS += dp[w.second].second;
            
            //merge PQ
            D.join(u, w.second);
        }
        dp[u] = {0, curS};
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int n,i; cin >> n;
    A.resize(n+1); dp.resize(n+1); D.init(n+1); E.resize(n+1); par.resize(n+1, -1);
    long long s; cin >> s;
    A[0] = s;
    i = 0; while (i++ < n) {
        cin >> A[i] >> par[i];
        E[par[i]].push_back(i);
    } 
    dfs(0); 
    //for (auto x: dp) cout << x.first << " " << x.second << "a\n";
    cout << dp[0].second-s;
    return 0;
}

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