Submission #1021214

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021214		coin_	Jobs (BOI24_jobs)	C++14	100 / 100	215 ms	61792 KiB

Main

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

const int maxn = 3e5 + 6;
struct brainrot{
    int fanumtax, skibidi;
    bool operator >(const brainrot &a) const{
        return (fanumtax == a.fanumtax ? skibidi > a.skibidi : (fanumtax > a.fanumtax));
    }
};

int val[maxn] = {0}, head[maxn] = {0};
vector<vector<int>> adj(maxn);
priority_queue<brainrot, vector<brainrot>, greater<brainrot>> sigma[maxn];

int small_to_large(int a, int b){
    if (sigma[a].size() > sigma[b].size()){
        swap(a, b);
    }
    while(!sigma[a].empty()){
        brainrot k = sigma[a].top();
        sigma[a].pop();
        sigma[b].push(k);
    }
    return b;
}

void sigmaification(int ptr, brainrot englishorspanish){
    priority_queue<brainrot, vector<brainrot>, greater<brainrot>> &mewing = sigma[ptr];
    while(!mewing.empty()){
        brainrot rizz = mewing.top();
        if (englishorspanish.skibidi <= 0){
            int newfanumtax = max(englishorspanish.fanumtax, rizz.fanumtax - englishorspanish.skibidi), newskibidi = rizz.skibidi + englishorspanish.skibidi; 
            englishorspanish = {newfanumtax, newskibidi};
            mewing.pop();
        }
        else{
            if (englishorspanish.fanumtax > rizz.fanumtax){
                englishorspanish = {englishorspanish.fanumtax, rizz.skibidi + englishorspanish.skibidi};
                mewing.pop();
            }
            else{
                mewing.push(englishorspanish);
                break;
            }
        }
    }
    if (mewing.empty()) mewing.push(englishorspanish);
    if (mewing.size() == 1 && mewing.top().skibidi <= 0) mewing.pop();
}

void dfs(int u, int p = -1){
    int counter = 1;
    if (adj[u].size() == 0) head[u] = u;
    for (int v: adj[u]){
        dfs(v, u);
        if (counter == 1){
            head[u] = head[v];
        }
        else{
            head[u] = small_to_large(head[u], head[v]);
        }
        counter++;
    }
    sigmaification(head[u], {max(0LL, -val[u]), val[u]});
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
    int n, s;
    cin >> n >> s;
    for (int i = 1; i <= n; i++){
        int p;
        cin >> val[i] >> p;
        adj[p].push_back(i);
    }

    dfs(0);

    int mogging = 0;
    while(!sigma[head[0]].empty()){
        brainrot rizz = sigma[head[0]].top();
        int tax = rizz.fanumtax, mog = rizz.skibidi;
        sigma[head[0]].pop();
        if (s + mogging >= tax) mogging += mog;
    }
    cout << mogging << endl;
}

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