oj.uz

Submission #994628

# Submission time Handle Problem Language Result Execution time Memory
994628 2024-06-08T02:48:15 Z kym Jobs (BOI24_jobs) C++14
11 / 100
 183 ms 58376 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 300005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
int n,init;
int A[MAXN], P[MAXN];
vector<int>child[MAXN];
void print(priority_queue<pi,vector<pi>,greater<pi>> * pq){
	priority_queue<pi,vector<pi>,greater<pi>> cur = *pq;
	while(cur.size()){
		cout << "{ " << cur.top().first << "|"<<cur.top().second<<" } | ";
		cur.pop();
	}
}
priority_queue<pi,vector<pi>,greater<pi>> * dfs(int x){
	priority_queue<pi,vector<pi>,greater<pi>> * pq = new priority_queue<pi,vector<pi>,greater<pi>>();
	for(auto v:child[x]){
		priority_queue<pi,vector<pi>,greater<pi>> * c = dfs(v);
		if(c->size() > pq->size())swap(c,pq);
		while(c->size()){
			pq->push(c->top());c->pop();
		}
	}
	if(A[x]>=0){
		pq->push({0,A[x]});
	} else{
		int s=A[x];
		while(s<0 && pq->size()){
			if(pq->top().second + s < 0){
				s+=pq->top().second;
				pq->pop();
			} else{
				pi c=pq->top();
				int rem=pq->top().second + s;
				pq->pop();
				pq->push({c.first,rem});
				s=0;
			}
		}
		int sum=0;
		while(pq->size() && pq->top().first < -A[x]){
			sum += pq->top().second;
			pq->pop();
		}
		if(sum){
			pq->push({-A[x],sum});
		}
	}
	//cerr<<x<<":";
	//print(pq);
	//cerr<<endl;
	return pq;
}
int32_t main() 
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> init;
	for(int i=1;i<=n;i++){
		cin>>A[i]>>P[i];
		child[P[i]].push_back(i);
	}
	priority_queue<pi,vector<pi>,greater<pi>> * pq =dfs(0);
	int ans=0;
	while(pq->size() && pq->top().first<=init){
		ans += pq->top().second;
		init += pq->top().second;
		pq->pop();
	}
	cout<<ans;
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 56132 KB Output is correct
2 Correct 130 ms 46088 KB Output is correct
3 Correct 106 ms 40564 KB Output is correct
4 Correct 100 ms 48188 KB Output is correct
5 Correct 99 ms 54464 KB Output is correct
6 Correct 89 ms 38184 KB Output is correct
7 Correct 154 ms 49852 KB Output is correct
8 Correct 117 ms 39664 KB Output is correct
9 Correct 106 ms 51132 KB Output is correct
10 Correct 100 ms 55948 KB Output is correct
11 Correct 183 ms 58376 KB Output is correct
12 Correct 152 ms 47296 KB Output is correct
13 Correct 169 ms 54856 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 11080 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Incorrect 3 ms 10844 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 11080 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Incorrect 3 ms 10844 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10844 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 2 ms 11080 KB Output is correct
5 Correct 3 ms 11100 KB Output is correct
6 Correct 2 ms 11100 KB Output is correct
7 Correct 3 ms 11100 KB Output is correct
8 Correct 2 ms 11100 KB Output is correct
9 Correct 2 ms 10844 KB Output is correct
10 Incorrect 3 ms 10844 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 56132 KB Output is correct
2 Correct 130 ms 46088 KB Output is correct
3 Correct 106 ms 40564 KB Output is correct
4 Correct 100 ms 48188 KB Output is correct
5 Correct 99 ms 54464 KB Output is correct
6 Correct 89 ms 38184 KB Output is correct
7 Correct 154 ms 49852 KB Output is correct
8 Correct 117 ms 39664 KB Output is correct
9 Correct 106 ms 51132 KB Output is correct
10 Correct 100 ms 55948 KB Output is correct
11 Correct 183 ms 58376 KB Output is correct
12 Correct 152 ms 47296 KB Output is correct
13 Correct 169 ms 54856 KB Output is correct
14 Correct 2 ms 10844 KB Output is correct
15 Correct 2 ms 10844 KB Output is correct
16 Correct 2 ms 10844 KB Output is correct
17 Correct 2 ms 11080 KB Output is correct
18 Correct 3 ms 11100 KB Output is correct
19 Correct 2 ms 11100 KB Output is correct
20 Correct 3 ms 11100 KB Output is correct
21 Correct 2 ms 11100 KB Output is correct
22 Correct 2 ms 10844 KB Output is correct
23 Incorrect 3 ms 10844 KB Output isn't correct
24 Halted 0 ms 0 KB -