Submission #1067160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1067160		_rain_	Jobs (BOI24_jobs)	C++14	100 / 100	204 ms	75392 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
#define debug false
 
const int maxn = 3e5;
i64 s;
vector<int> g[maxn+2];
int n , x[maxn+2];
struct NODE{	
	i64 sum;
	i64 require;
	bool operator > (const NODE& other) const{
		if (require != other.require) return require < other.require;
		return sum < other.sum;
	}
};
priority_queue<NODE,vector<NODE>,greater<NODE>> bag[maxn+2];
 
void dfs(int u , int p){
	for (auto& v : g[u]){
		if (v==p) continue;
		dfs(v,u);
		if (bag[v].size() > bag[u].size()) swap(bag[u] , bag[v]);
		while (bag[v].size()){
			bag[u].push(bag[v].top());
			bag[v].pop();
		}
		if (debug){
			cout << u << " " << v << '\n';
		}
	}
	i64 sum  = x[u] , require = min(0 , x[u]);
	while (bag[u].size()){
		i64 x = bag[u].top().sum , y = bag[u].top().require; 
		if (sum < 0){
			require = min(require , y + sum);
			sum += x;
			bag[u].pop();
		}
		else {
			if (require <= y){
				sum += x;
				bag[u].pop();
				continue;
			}
			bag[u].push({sum , require});
			break;
		}
	}
	if (bag[u].size()==0) bag[u].push({sum , require});
	if (bag[u].size()==1 && bag[u].top().sum < 0) bag[u].pop();
	return;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	cin >> n >> s;
	for (int i = 1; i <= n; ++i) {
		int p; cin >> x[i] >> p;
		g[p].push_back(i);
	}
	i64 profit = 0;
	dfs(0,-1);
	while (bag[0].size()){
		i64 x = bag[0].top().sum , y = bag[0].top().require;
		if (debug){
			cout << x << ' ' << y << '\n';
		}
		bag[0].pop();
		if (s + profit + y >= 0){
			profit += x;
		}
	}
	cout << profit;
}

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