Submission #1029276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029276		Otalp	Jobs (BOI24_jobs)	C++17	14 / 100	970 ms	1048576 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second
#define int ll


vector<int> q[300100];
ll a[300100];
ll dp[300100][2];
ll kto[300100];
int us[300100];
int p[300100];
ll pref[300100];
ll ddp[300100];
vector<pair<ll, ll>> d[300100];

void dfs(int v, int p){
    dp[v][0] = a[v];
    dp[v][1] = 0;
    for(int to: q[v]){
        if(to == p) continue;
        dfs(to, v);
        dp[v][0] += dp[to][0];
        dp[v][1] += dp[to][1];
    }
    if(dp[v][1] > dp[v][0]) kto[v] = 0;
    else kto[v] = 1;
    dp[v][1] = min(dp[v][1], dp[v][0]);
}


void dfs2(int v, int P, int k, ll sum){
    if(k == 1){ 
        k = kto[v];
    }
    pref[v] = sum;
    us[v] = k;
    p[v] = P;
    sum += a[v];
    for(int to: q[v]){
        if(to == P) continue;
        dfs2(to, v, k, sum);
    }
}

void dfs3(int v, int p){
    if(!kto[v]) return;
    ddp[v] = -1e18;
    if(a[v] >= 0) ddp[v] = pref[v];
    d[v].pb({pref[v], a[v]}); 
    for(int to: q[v]){
        if(to == p) continue;
        dfs3(to, v);
        for(pair<ll, ll> h: d[to]){
            if(h.ss + a[v] >= 0){
                ddp[v] = max(ddp[v], min(pref[v], h.ff));
            }
            d[v].pb({min(pref[v], h.ff), h.ss + a[v]});
        }
    }
}

set<pair<ll, ll>> dd;


void er(int v){
    for(int to: q[v]){
        if(to == p[v]) continue;   
        if(!kto[to]) continue;
        dd.insert({ddp[to] - pref[to], to});
    }
}

            







void solve(){
    ll n, s;
    cin>>n>>s;
    ll ans = s;
    for(int i=1; i<=n; i++){
        int l, r;
        cin>>l>>r;
        q[r].pb(i);
        q[i].pb(r);
        a[i] = l;
        ans += a[i];
    }
    dfs(0, -1);
    dfs2(0, -1, 1, 0);
    ans = 0;
    dfs3(0, -1);
    dd.insert({ddp[0], 0});
    while(dd.size()){
        auto g = *dd.rbegin();
        if(a[g.ss] + s < 0) break;
        //cout<<s<<'\n';
        //for(auto h: dd){
        //    cout<<h.ff<<' '<<h.ss<<'\n';
        //}
        s += a[g.ss];
        if(dd.find(g) == dd.end()){
            cout<<-1;
            return;
        }
        dd.erase(dd.find(g));
        er(g.ss);
        ans += a[g.ss];
    }
    cout<<ans<<'\n';



}

signed main(){
    solve();
}

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