oj.uz

Submission #1066854

# Submission time Handle Problem Language Result Execution time Memory
1066854 2024-08-20T08:09:01 Z _rain_ Jobs (BOI24_jobs) C++14
11 / 100
 198 ms 49532 KB 
#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){
			sum += x;
			require = min(require , y + sum);
			bag[u].pop();
		}
		else {
			if (require < y) {
				bag[u].pop();
				sum += x;
			}
			else {
				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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 47944 KB Output is correct
2 Correct 141 ms 37820 KB Output is correct
3 Correct 111 ms 32324 KB Output is correct
4 Correct 88 ms 41812 KB Output is correct
5 Correct 86 ms 49164 KB Output is correct
6 Correct 83 ms 33736 KB Output is correct
7 Correct 144 ms 41140 KB Output is correct
8 Correct 97 ms 32380 KB Output is correct
9 Correct 79 ms 45828 KB Output is correct
10 Correct 95 ms 49532 KB Output is correct
11 Correct 198 ms 48916 KB Output is correct
12 Correct 153 ms 41412 KB Output is correct
13 Correct 168 ms 46112 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 4 ms 17008 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 3 ms 17296 KB Output is correct
7 Correct 4 ms 16984 KB Output is correct
8 Correct 4 ms 17072 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Incorrect 3 ms 16988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 4 ms 17008 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 3 ms 17296 KB Output is correct
7 Correct 4 ms 16984 KB Output is correct
8 Correct 4 ms 17072 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Incorrect 3 ms 16988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 16988 KB Output is correct
2 Correct 4 ms 17008 KB Output is correct
3 Correct 4 ms 16988 KB Output is correct
4 Correct 4 ms 16988 KB Output is correct
5 Correct 5 ms 17496 KB Output is correct
6 Correct 3 ms 17296 KB Output is correct
7 Correct 4 ms 16984 KB Output is correct
8 Correct 4 ms 17072 KB Output is correct
9 Correct 3 ms 16988 KB Output is correct
10 Incorrect 3 ms 16988 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 47944 KB Output is correct
2 Correct 141 ms 37820 KB Output is correct
3 Correct 111 ms 32324 KB Output is correct
4 Correct 88 ms 41812 KB Output is correct
5 Correct 86 ms 49164 KB Output is correct
6 Correct 83 ms 33736 KB Output is correct
7 Correct 144 ms 41140 KB Output is correct
8 Correct 97 ms 32380 KB Output is correct
9 Correct 79 ms 45828 KB Output is correct
10 Correct 95 ms 49532 KB Output is correct
11 Correct 198 ms 48916 KB Output is correct
12 Correct 153 ms 41412 KB Output is correct
13 Correct 168 ms 46112 KB Output is correct
14 Correct 3 ms 16988 KB Output is correct
15 Correct 4 ms 17008 KB Output is correct
16 Correct 4 ms 16988 KB Output is correct
17 Correct 4 ms 16988 KB Output is correct
18 Correct 5 ms 17496 KB Output is correct
19 Correct 3 ms 17296 KB Output is correct
20 Correct 4 ms 16984 KB Output is correct
21 Correct 4 ms 17072 KB Output is correct
22 Correct 3 ms 16988 KB Output is correct
23 Incorrect 3 ms 16988 KB Output isn't correct
24 Halted 0 ms 0 KB -