Submission #1049503

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049503		aymanrs	Jobs (BOI24_jobs)	C++17	58 / 100	2084 ms	67408 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct node {
    int x=0;
    vector<node*> l;
    long long ms=LONG_LONG_MAX;
};
void dfs(node* n){
    for(node* c : n->l) dfs(c);
    if(n->x > 0) {
        n->ms = 0;
        return;
    }
    set<pair<int, node*>> se;
    long long s = n->x;
    n->ms = s;
    for(node* c : n->l) if(c->ms < LONG_LONG_MAX) se.insert({c->ms, c});
    while(s <= 0 && !se.empty()){
        node* c = se.begin()->second;
        se.erase(se.begin());
        n->ms = max(n->ms, c->ms-s);
        s += c->x;
        for(node* u : c->l) if(u->ms < LONG_LONG_MAX) se.insert({u->ms, u});
    }
    if(s <= 0) n->ms = LONG_LONG_MAX;
}
void solve(){
    int n;
    long long s, os;cin >> n >> s;
    os = s;
    node g[n+1];
    for(int i = 1;i <= n;i++){
        int p;cin >> g[i].x >> p;
        g[p].l.push_back(&g[i]);
    }
    set<pair<long long, node*>> se;
    dfs(&g[0]);
    if(g[0].ms < LONG_LONG_MAX) se.insert({g[0].ms, &g[0]});
    while(!se.empty() && s >= se.begin()->first){
        node* c = se.begin()->second;
        se.erase(se.begin());
        s += c->x;
        for(node* u : c->l) if(u->ms < LONG_LONG_MAX) se.insert({u->ms, u});
    }
    cout << s-os << '\n';

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

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