Submission #1049418

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049418		aymanrs	Jobs (BOI24_jobs)	C++17	14 / 100	661 ms	1048576 KiB

Main

#include<bits/stdc++.h>
using namespace std;
struct node {
    node* p;
    long long x,m=-1;
    vector<node*> l, sub;
    bool v = false;
};
void dfs(node* n, long long t, long long mi, set<pair<int, node*>>& s){
    n->sub.clear();
    n->sub.push_back(n);
    t += n->x;
    mi = min(mi, t);
    if(t > 0){
        s.insert({-mi, n});
        n->m = -mi;
        return;
    }
    for(node* c : n->l){
        if(c->v) continue;
        dfs(c, t, mi, s);
        for(node* x : c->sub) n->sub.push_back(x);
    }
}
void solve(){
    int n;cin >> n;
    long long s;cin >> s;
    long long 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]);
        g[i].p = &g[p];
    }
    set<pair<int, node*>> se;
    g[0].x=0;
    dfs(&g[0], 0, 0, se);
    g[0].v=true;
    while(!se.empty() && se.begin()->first <= s){
        node* u = se.begin()->second;
        if(u->m != se.begin()->first){
            se.erase(se.begin());
            continue;    
        }
        se.erase(se.begin());
        while(!u->v){
            u->v=true;
            s += u->x;
            u->m = -1;
            for(node* j : u->l) if(!j->v) {
                for(node* c : j->sub) if(c->m != -1) {
                    se.erase({c->m,c});
                    c->m=-1;
                }
                dfs(j,0,0,se);
            }
            u=u->p;
        }
    }
    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: 0 / 15
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31