Submission #1155657

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155657		adiyer	Jobs (BOI24_jobs)	C++20	100 / 100	404 ms	59652 KiB

Main

#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define len(x) (ll) x.size()
#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;

const int N = 3e5 + 11;
const ll inf = 2e18 + 12;

ll n, s, prf;
ll p[N], a[N], rt[N];

vector < ll > g[N];

struct node{
    ll r, p;
    bool operator >(const node &x) const {
        if(r == x.r) return p > x.p;
        else return r > x.r;
    }
};

priority_queue < node, vector < node >, greater < node > > q[N];

ll mrg(ll x, ll y){
    if(len(q[x]) < len(q[y])) swap(x, y);
    while(len(q[y])) q[x].push(q[y].top()), q[y].pop();
    return x;
}

void cmb(ll v, node x){
    while(len(q[v])){
        node u = q[v].top();
        if(x.p <= 0) q[v].pop(), x = {max(x.r, u.r - x.p), u.p + x.p};
        else{
            if(x.r > u.r) q[v].pop(), x = {x.r, u.p + x.p};
            else{ 
                q[v].push(x); 
                break;
            }
        }
    }
    if(q[v].empty()) q[v].push(x);
    if(len(q[v]) == 1 && q[v].top().p <= 0) q[v].pop();
}

void dfs(ll v){
    if(g[v].empty()) rt[v] = v;
    for(ll u : g[v]){
        dfs(u);
        if(!rt[v]) rt[v] = rt[u];
        else rt[v] = mrg(rt[v], rt[u]);
    }
    cmb(rt[v], {max(0ll, -a[v]), a[v]});
}

signed main(){
    cin >> n >> s, prf = s;
    for(ll i = 1; i <= n; i++) cin >> a[i] >> p[i], g[p[i]].pb(i);
    dfs(0);
    ll v = rt[0];
    while(len(q[v])){
        if(prf >= q[v].top().r) prf += q[v].top().p;
        q[v].pop();
    }
    cout << prf - s;
}

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