제출 #1066278

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1066278		anton	Jobs (BOI24_jobs)	C++17	43 / 100	2069 ms	99004 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;

struct merger{
    vector<vector<pii>> groups;
    priority_queue<pii> ev;

    void add(vector<pii> vals){
        int id = groups.size();
        groups.push_back(vals);
        if(vals.size()>0){
            ev.push({vals.back().first, id});
        }
    }

    bool empty(){
        return ev.size()==0;
    }

    pii get(){
        pii cords = ev.top();
        ev.pop();
        pii val = groups[cords.second].back();
        groups[cords.second].pop_back(); 
        if(groups[cords.second].size()>0){
            ev.push({groups[cords.second].back().first, cords.second});
        }
        return val;
    }
};
    
vector<pii> dfs(int i){


    merger m;
    for(auto e: ch[i]){
        m.add(dfs(e));
    }


    vector<pii> ev;

    while(!m.empty()){
        ev.push_back(m.get());
    }
    reverse(ev.begin(), ev.end());
    ev.push_back({x[i], x[i]});


    while(ev.size()>1 && ev.back().second<0){
        pii cur = ev.back();
        ev.pop_back();
        ev.back().second += cur.second;
        ev.back().first = min(ev.back().first + cur.second, cur.first);
    }

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

    int cur_s = 0;
    int cost = 0;

    
    vector<pii> res;

    while(ev.size()>0){
        
        pii cur_stats= ev.back();
        ev.pop_back();
        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({cur_stats.first, cur_stats.second});
    }
    
    

    if(res.back().second<0){
        return {};
    }
    reverse(res.begin(), res.end());
    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+S>=0){
        S+= ev.back().second;
        ev.pop_back();
    }

    cout<<S-init_s<<endl;
}

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