제출 #1054991

#제출 시각아이디문제언어결과실행 시간메모리
1054991anangoJobs (BOI24_jobs)C++17
0 / 100
121 ms33716 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...