Submission #1065922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065922		anton	Jobs (BOI24_jobs)	C++17	0 / 100	598 ms	30864 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;
    
vector<vector<int>> ch;
vector<int> x;
    
vector<pii> dfs(int i){
    vector<pii> res;


    priority_queue<pii> ev;
    vector<vector<pii>> ch_res;
    for(auto e: ch[i]){
        ch_res.push_back(dfs(e));
        if(ch_res.back().size()>0){
            ev.push({ch_res.back().back().first, ch_res.size()-1});
        }
    }

    int cur_s = x[i];
    int cost = 0;

    

    while(ev.size()>0){
        pii cur_ev = ev.top();
        pii cur_stats= ch_res[cur_ev.second].back();
        ch_res[cur_ev.second].pop_back();
        ev.pop();

        if(ch_res[cur_ev.second].size()>0){
            ev.push({ch_res[cur_ev.second].back().first,cur_ev.second});
        }

        if(cur_stats.first+cur_s>=0){
        }
        else{
            cost += cur_stats.first+cur_s;
            cur_s = -cur_stats.first;
        }
        cur_s += cur_stats.second;
        res.push_back({cost, cur_stats.second});
    }

    
    sort(res.begin(), res.end());
    if(x[i]>=0){
        res.push_back({0, 0});
    }
    
    
    if(res.size()>0){
        res.back().first = min(x[i], res.back().first+x[i]);
        res.back().second +=x[i];
    }

    return res;
}
signed main(){
    cin>>N>>S;
    x.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);
    }

    auto ev = dfs(0);

    int init_s= S;

    while(ev.size()>0 && ev.back().first+S>=0){
        S+= ev.back().second;
        ev.pop_back();
    }

    cout<<S-init_s<<endl;
}

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