제출 #1065951

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1065951		anton	Jobs (BOI24_jobs)	C++17	0 / 100	2052 ms	50520 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 = 0;
    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());
    
    res.push_back({x[i], x[i]});
    while(res.size()>1 && res.back().second<0){
        pii cur = res.back();
        res.pop_back();
        res.back().second += cur.second;
        res.back().first = min(res.back().first + cur.first, cur.first);
    }

    if(res.back().second<0){
        return {};
    }

    return res;
}
signed main(){
    cin>>N>>S;
    x.resize(N+1, 0);
    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+init_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