Submission #1178705

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178705		gyg	Jobs (BOI24_jobs)	C++20	100 / 100	287 ms	48844 KiB

Main

#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
#define fir first 
#define sec second
using namespace std;

const int N_MAX = 300000;



int x[N_MAX + 1];
vector <int> children[N_MAX + 1];

// Index of the 'leader' vertex of a priority queue containing vertex i
int p_queue_index[N_MAX + 1];
// Structure allowing to extract block with the smallest "requirement" value
priority_queue <pii, vector<pii>, greater<pii>> blocks[N_MAX + 1];


int merge_priority_queues(int id_a, int id_b) {
    if (blocks[id_b].size() > blocks[id_a].size()) {
        // Trick: merge smaller queue to a larger one
        swap(id_a, id_b);
    }
    while (blocks[id_b].size() > 0) {
        blocks[id_a].push(blocks[id_b].top());
        blocks[id_b].pop();
    }
    return id_a;
}


// Combine new_block with the current list of blocks at vertex v until the sum of the new_block becomes positive
void combine_blocks(int v, pii new_block) {
    // while (blocks[v].size() > 0) {
    //     block top_block = blocks[v].top();
    //     if (new_block.sum <= 0) {
    //         blocks[v].pop();
    //         new_block = {max(new_block.requirement, top_block.requirement - new_block.sum), new_block.sum + top_block.sum};
    //     }
    //     else {
    //         // If sum is positive, we want to keep "requirement" sorted in non-decreasing order
    //         if (new_block.requirement > top_block.requirement) {
    //             blocks[v].pop();
    //             new_block = {new_block.requirement, new_block.sum + top_block.sum};
    //         }
    //         else {
    //             // new_block satisfies the requirements, push it to the list of the blocks at vertex v.
    //             blocks[v].push(new_block);
    //             break;
    //         }
    //     }
    // }
    // if (blocks[v].size() == 0) {
    //     blocks[v].push(new_block);
    // }
    // if (blocks[v].size() == 1 && blocks[v].top().sum <= 0) {
    //     blocks[v].pop();
    // }

    while (blocks[v].size() && (new_block.sec <= 0 || new_block > blocks[v].top())) {
        pii top_block = blocks[v].top(); 
        blocks[v].pop();
        new_block = {max(new_block.fir, top_block.fir - new_block.sec), new_block.sec + top_block.sec};
    }
    if (new_block.sec <= 0) return;
    blocks[v].push(new_block);
}


void dfs(int v) {
    if (children[v].size() == 0) {
        // For a new priority queue, set the graph child node as the 'leader' of the priority queue
        p_queue_index[v] = v;
    }
    for (int i = 0; i < children[v].size(); i++) {
        int a = children[v][i];
        dfs(a);
        if (i == 0) {
            p_queue_index[v] = p_queue_index[a];
        }
        else {
            // Merge priority queues of children vertices
            p_queue_index[v] = merge_priority_queues(p_queue_index[v], p_queue_index[a]);
        }
    }
    // Add block formed by vertex v to the list of merged blocks from children of v
    combine_blocks(p_queue_index[v], {max(0, -x[v]), x[v]});
}


int main() {
    int N;
    long long s, profit = 0;  // Profit starts from 0, and not from s.
    cin >> N >> s;
    for (int i = 1; i <= N; i++) {
        int p;
        cin >> x[i] >> p;
        children[p].push_back(i);
    }

    // Perform dfs which constructs the order of blocks to be visited independently on the s.
    dfs(0);

    // Once the block order is set, take all blocks that we can with the given value of s.
    while (blocks[p_queue_index[0]].size() > 0) {
        long long min_requirement = blocks[p_queue_index[0]].top().fir;
        long long sum = blocks[p_queue_index[0]].top().sec;
        blocks[p_queue_index[0]].pop();
        if (s + profit >= min_requirement) {
            profit += sum;
        }
    }

    cout << profit << endl;
    return 0;
}

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