Submission #998590

#	Time	Username	Problem	Language	Result	Execution time	Memory
998590		vjudge1	Jobs (BOI24_jobs)	C++17	0 / 100	240 ms	64464 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define int long long

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(!stack[v].empty() && 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);
		else break;
	}
	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, INF); //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";
}

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