oj.uz

Submission #1064740

# Submission time Handle Problem Language Result Execution time Memory
1064740 2024-08-18T17:18:30 Z anango Jobs (BOI24_jobs) C++17
0 / 100
 465 ms 65468 KB 
#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();
        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);
        }
        parent[i] = prereq;
    }
    for (int i=0; i<n; i++) {
        random_shuffle(sons[i].begin(), sons[i].end());
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> final_result;
    for (int root=0; root<n; root++) {
        if (parent[root]==-1) {
            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 << cursum <<" " << best.first <<" " << best.second << endl;
        if (best.second<0) continue;
        if (best.first>cursum) break;
        cursum+=best.second;
    }
    int proooooooooofit = cursum-s;
    cout << proooooooooofit << endl;
    
    
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 465 ms 65468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 465 ms 65468 KB Output isn't correct
2 Halted 0 ms 0 KB -