Submission #1095147

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095147		SalihSahin	Jobs (BOI24_jobs)	C++14	100 / 100	166 ms	79696 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int N = 3e5 + 5;
const int K = 20;
const int mod = 1e9 + 7;

vector<int> adj[N], x(N), p(N), gett(N);
vector<int> radj[N], lstadj[N];

void calc(int node, int lastpar){
    if(x[node] >= 0){
        gett[lastpar] += x[node];
        for(auto itr: adj[node]){
            calc(itr, lastpar);
        }
    }
    else{
        radj[lastpar].pb(node);
        for(auto itr: adj[node]){
            calc(itr, node);
        }
    }
}

void make_good(int node){
    for(auto itr: radj[node]){
        make_good(itr);
    }
    priority_queue<array<int, 2> > pq;
    for(auto itr: radj[node]){
      if(x[itr] <= gett[itr]) pq.push({-x[itr], itr});
    }

    int wh = gett[node] - x[node];

    while(pq.size() && x[node] > gett[node]){
        int cst = -pq.top()[0];
        int u = pq.top()[1];
        pq.pop();

        gett[node] += (gett[u] - x[u]);
        int nw = x[node];
        x[node] = max(x[node], -(wh - cst));
        gett[node] += (x[node] - nw);
        wh += (gett[u] - x[u]);

        for(auto itr: lstadj[u]){
           pq.push({-x[itr], itr});
        }
    }

    if(x[node] <= gett[node]){
        while(!pq.empty()){
            int u = pq.top()[1];
            lstadj[node].pb(u);
            pq.pop();
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, s;
    cin>>n>>s;

    for(int i = 1; i <= n; i++){
        cin>>x[i]>>p[i];
        adj[p[i]].pb(i);
    }
    calc(0, 0); // suan bad ve good nodelar var öyle ki x[i] ödeyebiliyorsan get[i] kazanabiliyorsun
    for(int i = 0; i <= n; i++) x[i] = -x[i]; // costa çevirdim
    make_good(0);
    int now = s;
    priority_queue<pair<int, int> > pq;
    pq.push({-x[0], 0});
    while(pq.size()){
        int u = pq.top().second;
        pq.pop();
        if(x[u] > now) break;
        now = (now - x[u] + gett[u]);
        for(auto itr: lstadj[u]){
            pq.push({-x[itr], itr});
        }
    }

    cout<<now - s<<endl;
    return 0;
}

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