Submission #1049398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049398		aymanrs	Jobs (BOI24_jobs)	C++17	29 / 100	144 ms	36244 KiB

Main

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