제출 #999086

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999086		esomer	Jobs (BOI24_jobs)	C++17	100 / 100	341 ms	104656 KiB

Main

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll INF = 2e18;

void DFS(int v, vector<vector<int>>& adj, vector<ll>& dp, vector<int>& x, vector<multiset<pair<ll, ll>>>& stack){
	for(int node : adj[v]){
		DFS(node, adj, dp, x, stack);
		if((int)stack[node].size() > (int)stack[v].size()) swap(stack[node], stack[v]);
		for(pair<ll, ll> pr : stack[node]){ //Not so complex now, as I am maintaining sum only.
			stack[v].insert(pr);
		}
	}
	// cout << "v "<< v << " stack:\n";
	// for(pair<int, int> pr : stack[v]) cout << pr.first << " "<< pr.second << "\n";
	ll minPre = max(0, -x[v]); //The max 0 is just if it's positive. For convenience, i don't want it to be neg. 
	ll sum = x[v];
	while(sum <= 0 && !stack[v].empty()){
		pair<ll, ll> pr = *stack[v].begin(); stack[v].erase(stack[v].begin());
		minPre = max(minPre, pr.first - sum); sum += pr.second;
	}
	if(sum <= 0){
		//Here the stack is already empty.
		return;
	}
	//Now, because I am the root, my children can't be taken without me, so I need to erase the ones
	//with minPre lower than mine.
	while(!stack[v].empty() && (*stack[v].begin()).first < minPre){
		pair<ll, ll> pr = *stack[v].begin(); stack[v].erase(stack[v].begin());
		sum += pr.second;
	}
	stack[v].insert({minPre, sum});
	// cout << "v "<< v << " stack:\n";
	// for(pair<int, int> pr : stack[v]) cout << pr.first << " "<< pr.second << "\n";
	dp[v] = minPre;
	// cout << "dp "<< dp[v] << "\n";
}

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);
	for(int i = 0; i < N; i++){
		cin >> x[i] >> p[i]; p[i]--;
		if(p[i] != -1){
			adj[p[i]].push_back(i);
		}
	}
	vector<ll> dp(N, INF); //Min cost until profit.
	vector<multiset<pair<ll, ll>>> stack(N);
	for(int i = 0; i < N; i++){
		if(p[i] == -1) DFS(i, adj, dp, x, 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: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 29 / 29
• Subtask 5: 31 / 31