Submission #1147872

#	Time	Username	Problem	Language	Result	Execution time	Memory
1147872		kirakaminski968	Jobs (BOI24_jobs)	C++20	100 / 100	306 ms	44100 KiB

Main

#include <iostream>
#include <bits/extc++.h>
#define ll long long
using namespace std;
#define heap __gnu_pbds::priority_queue<int, cmp, __gnu_pbds::pairing_heap_tag>
const int MAXN = 3e5+5;
ll need[MAXN],sum[MAXN],val[MAXN];
vector<int> adj[MAXN];
struct cmp{
    bool operator()(int x, int y){
        return need[x] > need[y];
    }
};
heap pq[MAXN];
void push(int u){
    ll cur = 0; pq[u].push(u);
    need[u] = 0;
    //cout << u << "\n";
    while(!pq[u].empty()){
        int x = pq[u].top(); pq[u].pop();
        //cout << x << " " << need[x] << "\n";
        if(need[x] == 2e18) continue;
        if(cur < need[x]){
            need[u] += need[x]-cur;
            cur = need[x];
        }
        if(x == u){
            cur += val[u];
            for(auto v : adj[u]){
                pq[u].push(v);
            }
        }
        else{
            cur += sum[x];
            if(pq[u].size() < pq[x].size()) pq[u].swap(pq[x]);
            pq[u].join(pq[x]);
        }
        if(cur > need[u]){
            sum[u] = cur-need[u];
            //cout << u << " " << need[u] << "\n";
            return;
        }
    }
    need[u] = 2e18;
}
void dfs(int u){
    for(auto v : adj[u]){
        dfs(v);
    }
    push(u);
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N; ll S; cin >> N >> S;
    for(int i = 1;i<=N;++i){ //add a node 0 to connect them all
        cin >> val[i+1];
        int p; cin >> p;
        adj[p+1].push_back(i+1);
    }
    dfs(1);
    heap q; ll cur = S;
    q.push(1);
    while(!q.empty()){
        int u = q.top(); q.pop();
        //cout << u << " " << need[u] << " " << val[u]  << " " << cur << "\n";
        if(cur < need[u]) break;
        cur += val[u];
        for(auto v : adj[u]){
            q.push(v);
        }
    }
    cout << cur-S << "\n";
    return 0;
}

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