Submission #1080936

#	Time	Username	Problem	Language	Result	Execution time	Memory
1080936		anton	Jobs (BOI24_jobs)	C++17	11 / 100	479 ms	60336 KiB

Main

#include<bits/stdc++.h>


using namespace std;
#define int long long
#define pii pair<int, int>

const int MAX_N = 3e5+1;
int N, S;


pii merge_ev(pii a,pii b){
    return {min(a.first, b.first+a.second), a.second+b.second};
}  
struct Investment{
    priority_queue<pii> ev;
    int delta= 0;
    void insert(pii e){
        ev.push({e.first-delta, e.second-delta});
    }

    void merge(Investment b){
        while(b.ev.size()>0){
            auto e = b.ev.top();
            b.ev.pop();
            insert({e.first+b.delta, e.second+b.delta});
        }
    }
};


vector<vector<int>> ch;
vector<int> x;
vector<Investment> inv;

void dfs(int u){
    for(auto e: ch[u]){
        dfs(e);
        if(inv[e].ev.size()>inv[u].ev.size()){
            swap(inv[e], inv[u]);
        }
        inv[u].merge(inv[e]);
    }

    pii first_elem = {min(0LL, x[u]), x[u]};
    while(inv[u].ev.size()>0 && (first_elem.first<0 || first_elem.second>=inv[u].ev.top().second)){
        first_elem = merge_ev(first_elem, inv[u].ev.top());
        inv[u].ev.pop();
    }

    if(first_elem.second>0){
        inv[u].insert(first_elem);
    }
}


signed main(){
    cin>>N>>S;
    x.resize(N+1, 0);
    inv.resize(N+1);
    ch.resize(N+1);
    for(int i = 0; i<N; i++){
        int p;
        cin>>x[i+1]>>p;
        ch[p].push_back(i+1);
    }
 
    dfs(0);
 
    auto inv0 = inv[0];
    int init_s= S;
 
    
    while(inv0.ev.size()>0 && inv0.ev.top().first+S>=0){
        S+= inv0.ev.top().second;
        inv0.ev.pop();
    }
 
    cout<<S-init_s<<endl;
}

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