| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 998587 |
2024-06-14T09:43:45 Z |
vjudge1 |
Jobs (BOI24_jobs) |
C++17 |
|
2000 ms |
38996 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 2e18;
vector<ll> orderedSum; //For binary search purposes, reduces constant significantly.
void updateDp(int v, vector<ll>& dp, vector<ll>& sum, vector<int>& x, vector<set<pair<ll, ll>>>& stack){
int lo = 0;
int hi = (int)orderedSum.size() - 1;
while(lo <= hi){
int mid = (lo + hi) / 2;
auto it = stack[v].upper_bound({orderedSum[mid], INF});
if(it == stack[v].begin()){
//I don't have any minPre so low in stack, so I can go higher.
lo = mid + 1;
continue;
}
it--;
ll mnPre = (*it).first;
ll mxPre = (*it).second;
// cout << "Mid "<< mid << " minPre " << mnPre << " maxPre "<< mxPre << "\n";
if(mxPre >= sum[v] - x[v]){
dp[v] = min(dp[v], -mnPre);
lo = mid + 1; //I can go higher, try for bigger minPre.
}else hi = mid - 1;
}
// cout << "dp "<< dp[v] << "\n";
// cout << "Ending v "<< v << " stack:\n";
// for(pair<ll, ll> p : stack[v]){
// cout << p.first << " " << p.second << "\n";
// }
}
void DFS(int v, vector<vector<int>>& adj, vector<ll>& dp, vector<int>& x, vector<ll>& sum, vector<set<pair<ll, ll>>>& stack){
for(int node : adj[v]){
DFS(node, adj, dp, x, sum, stack);
if((int)stack[node].size() > (int)stack[v].size()) swap(stack[node], stack[v]);
//I need to add first the oldest (i.e. with less prefix min.) to maintain the
//order of the the one I'm adding.
for(pair<ll, ll> pr : stack[node]){
ll maxPre = pr.second;
//Here, I should not erase prefix mins that are bigger then me, because
//they are parallel. I should only erase smaller prefix mins which smaller
//maxPre, because they are useless. This way, smaller prefix mins will
//always have bigger maxPre, and I can do binary search.
//I should also be careful to not add it if there is one with minPre
//>= me and also a maxPre >= me.
auto it = stack[v].lower_bound(pr);
if(it != stack[v].end() && (*it).second >= maxPre){
//Then I am useless, so I skip.
continue;
}
//Here I need to check if I can erase some.
it = stack[v].lower_bound(pr);
while(it != stack[v].begin()){
it--;
if((*it).second <= maxPre){
//Then it is useless, so I erase it.
stack[v].erase(it);
}else break;
it = stack[v].lower_bound(pr);
}
stack[v].insert(pr);
}
}
//Add me.
//When adding me, I need to erase 100% the ones with prefixMin > me.
//because that won't be possible anymore.
//Then, when only prefixMin <= me are left, I go from bigger to smaller and only
//erase the next one if it's useless, i.e., its prefixMax is <= than mine.
//Also careful, if there is one with prefixMin == me and its prefixMax is bigger than mine,
//I will not add myself.
// cout << "Initial v "<< v << " stack:\n";
// for(pair<ll, ll> p : stack[v]){
// cout << p.first << " " << p.second << "\n";
// }
ll minPre = sum[v];
ll maxPre = sum[v];
auto it = stack[v].lower_bound({minPre, INF}); //i.e they have p.first > minPre.
while(it != stack[v].end()){
maxPre = max(maxPre, (*it).second); //I update the maxPrefix.
stack[v].erase(it);
it = stack[v].lower_bound({minPre, INF});
}
if(stack[v].empty()){
stack[v].insert({minPre, maxPre});
//I need to update dp here.
updateDp(v, dp, sum, x, stack);
return;
}
pair<ll, ll> lst = *stack[v].rbegin();
if(lst.first == minPre && lst.second >= maxPre){
updateDp(v, dp, sum, x, stack);
//I'm useless.
return;
}
while(!stack[v].empty()){
auto it = stack[v].end(); it--;
if((*it).second <= maxPre) stack[v].erase(it);
}
stack[v].insert({minPre, maxPre});
//Now, I calculate the DP with binary search.
//I want the maximum minPre, so that -(minPre - (sum[v] - x[v])) is minimum,
//which is the cost, such that its maxPre is maxPre - (sum[v] - x[v]) is >= 0.
//which means that maxPre >= sum[v] - x[v].
updateDp(v, dp, sum, x, stack);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int N; ll s; cin >> N >> s;
ll orgs = s;
vector<int> x(N), p(N);
vector<vector<int>> adj(N);
vector<ll> sum(N, 0);
for(int i = 0; i < N; i++){
cin >> x[i] >> p[i]; p[i]--;
if(p[i] != -1){
adj[p[i]].push_back(i);
sum[i] = sum[p[i]];
}
sum[i] += x[i];
}
orderedSum = sum;
sort(orderedSum.begin(), orderedSum.end());
vector<ll> dp(N, 2e18); //Min cost until profit.
vector<set<pair<ll, ll>>> stack(N);
for(int i = 0; i < N; i++){
if(p[i] == -1) DFS(i, adj, dp, x, sum, stack);
}
priority_queue<pair<ll, int>> q;
for(int i = 0; i < N; i++){
if(p[i] == -1){
q.push({-dp[i], i});
}
}
while(!q.empty() && -q.top().first <= s){
int v = q.top().second; q.pop();
s += x[v];
for(int node : adj[v]){
q.push({-dp[node], node});
}
}
cout << s - orgs << "\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
38996 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2055 ms |
348 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
38996 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
