Submission #1081199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1081199		anton	Jobs (BOI24_jobs)	C++17	100 / 100	345 ms	90816 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 display(Investment e){
    while(e.ev.size()>0){
        auto t = e.ev.top();
        e.ev.pop();
    }
}
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.second<0 || first_elem.first<=inv[u].ev.top().first)){
        //cout<<"merging "<<first_elem.first<<" "<<first_elem.second<<" "<<inv[u].ev.top().first<<" "<<inv[u].ev.top().second<<endl;
        first_elem = merge_ev(first_elem, inv[u].ev.top());
        inv[u].ev.pop();
    }

    if(first_elem.second>0){
        inv[u].insert(first_elem);
    }
    //cout<<u<<endl;
    //display(inv[u]);
}


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;
}

Compilation message (stderr)

Main.cpp: In function 'void display(Investment)':
Main.cpp:38:14: warning: variable 't' set but not used [-Wunused-but-set-variable]
   38 |         auto t = e.ev.top();
      |              ^

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