oj.uz

Submission #1065970

# Submission time Handle Problem Language Result Execution time Memory
1065970 2024-08-19T13:43:35 Z anton Jobs (BOI24_jobs) C++17
0 / 100
 2000 ms 50488 KB 
#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.second, 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.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 27448 KB Output is correct
2 Correct 234 ms 28044 KB Output is correct
3 Correct 201 ms 36088 KB Output is correct
4 Execution timed out 2064 ms 50488 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 483 ms 27448 KB Output is correct
2 Correct 234 ms 28044 KB Output is correct
3 Correct 201 ms 36088 KB Output is correct
4 Execution timed out 2064 ms 50488 KB Time limit exceeded
5 Halted 0 ms 0 KB -