Submission #1054991

#	Time	Username	Problem	Language	Result	Execution time	Memory
1054991		anango	Jobs (BOI24_jobs)	C++17	0 / 100	121 ms	33716 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> 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) {
    for (int j:sons[node]) {
        dfs(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();
        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);
    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);
        }
    }
    int c = 1000;
    int root = rand(); while (c--) root+=rand();
    root%=n; root+=n; root%=n;
    dfs(root);
    int cursum = s;
    for (pair<int,int> o:set_conversion(needfuls[root])) {
        if (cursum<o.first) break;
        cursum+=o.second;
    }
    int proooooooooofit = cursum-s;
    cout << proooooooooofit << endl;
    
    
}

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