Submission #1055055

#	Time	Username	Problem	Language	Result	Execution time	Memory
1055055		anango	Jobs (BOI24_jobs)	C++17	58 / 100	290 ms	89572 KiB

Main

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

vector<vector<int>> sons;
int n,s;
vector<int> vals;
vector<int> visited;
vector<int> parent;
vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>> needfuls;

set<pair<int,int>> set_conversion(priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> nv) {
    set<pair<int,int>> S;
    while (nv.size()) {
        S.insert(nv.top()); nv.pop();
    }
    return S;
}

void dfs(int node) {
    visited[node] = 1;
    for (int j:sons[node]) {
        dfs(j);
        if (needfuls[node].size()<needfuls[j].size()) {
            swap(needfuls[node],needfuls[j]);
        }
        for (pair<int,int> k:set_conversion(needfuls[j])) {
            needfuls[node].push(k);
        }
    }
    
    int requirement,cursum;
    cursum = vals[node];
    if (vals[node]<0) {
        requirement = -vals[node];
    }
    else {
        requirement = 0;
    }
    while (needfuls[node].size() && cursum<0) {
        pair<int,int> best = needfuls[node].top(); needfuls[node].pop();
        requirement = max(requirement, best.first-cursum);
        cursum+=best.second;
    }
    while (needfuls[node].size() && needfuls[node].top().first-cursum<=requirement) {
        pair<int,int> best = needfuls[node].top(); needfuls[node].pop();
        requirement = max(requirement, best.first-cursum);
        cursum+=best.second;
    }
    if (cursum>0) {
        needfuls[node].push({requirement,cursum});
    }
    
}

signed main() {
    #ifndef ONLINE_JUDGE
        // for getting input from input.txt
        //freopen("input.txt", "r", stdin);
        // for writing output to output.txt
        //freopen("output.txt", "w", stdout);
    #endif
    #ifdef ONLINE_JUDGE
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);
    #endif //fast IO
    cin >> n >> s;
    parent=vector<int>(n,-1);
    sons=vector<vector<int>>(n);
    vals=vector<int>(n);
    visited=vector<int>(n,0);
    needfuls=vector<priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>>(n);
    for (int i=0; i<n; i++) {
        int val,prereq; cin >> val >> prereq; prereq--;
        vals[i] = val;
        if (prereq!=-1) {
            sons[prereq].push_back(i);
        }
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> final_result;
    for (int root=0; root<n; root++) {
        if (!visited[root]) {
            dfs(root);
            for (auto j:set_conversion(needfuls[root])) {
                final_result.push(j);
            }
        }
    }
    int cursum = s;
    while (final_result.size()) {
        pair<int,int> best = final_result.top(); final_result.pop();
        //cout << best.first <<" " << best.second << endl;
        if (best.first>cursum) break;
        cursum+=best.second;
    }
    int proooooooooofit = cursum-s;
    cout << proooooooooofit << endl;
    
    
}

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