oj.uz

Submission #995128

# Submission time Handle Problem Language Result Execution time Memory
995128 2024-06-08T13:39:24 Z LCJLY Jobs (BOI24_jobs) C++14
11 / 100
 329 ms 100144 KB 
#include <bits/stdc++.h>
using namespace std;
	
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
 
vector<int>adj[300005];
int arr[300005];
multiset<pii>se[300005];
int ans=0;
 
void dfs(int index){
	for(auto it:adj[index]){
		dfs(it);
		//for(auto ii:se[it]) se[index].insert(ii);
		if(se[index].size()<se[it].size()) swap(se[index],se[it]);
		for(auto ii:se[it]) se[index].insert(ii);
	}
 
	//big small
	int counter=arr[index];
	int need=max(0LL,-arr[index]);
	while(counter<0){
		if(se[index].empty()) break;
		//greedily take the smallest 
		pii hold=*se[index].begin();
		se[index].erase(se[index].begin());
		counter+=hold.second;
		need=max(need,-counter+hold.first);
	}
	if(counter>0){
		//consuming
		se[index].insert({need,counter});
	}
	ans=counter;
	//show(index,index);
	//for(auto it:se[index]){
		//cout << it.first << " " << it.second << endl;
	//}
}
 
void solve(){	
	int n,m;
	cin >> n >> m;
	
	int temp,temp2;
	for(int x=1;x<=n;x++){
		cin >> temp >> temp2;
		arr[x]=temp;
		adj[temp2].push_back(x);
	}
	arr[0]=0;
	dfs(0);
	int cur=m;
	while(!se[0].empty()&&se[0].begin()->first<=cur){
		//pii hold=*se[0].begin();
		//show2(hold.first,hold.first,hold.second,hold.second);
		cur+=se[0].begin()->second;
		se[0].erase(se[0].begin());
	}
	//show(cur,cur);
	cout << cur-m;
}
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	//freopen("in.txt","r",stdin);
	while(t--){
		solve();
	}
}

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 93524 KB Output is correct
2 Correct 253 ms 67852 KB Output is correct
3 Correct 193 ms 50128 KB Output is correct
4 Correct 147 ms 53588 KB Output is correct
5 Correct 106 ms 62036 KB Output is correct
6 Correct 154 ms 56400 KB Output is correct
7 Correct 238 ms 76372 KB Output is correct
8 Correct 236 ms 50200 KB Output is correct
9 Correct 131 ms 58708 KB Output is correct
10 Correct 99 ms 62800 KB Output is correct
11 Correct 329 ms 100144 KB Output is correct
12 Correct 278 ms 84304 KB Output is correct
13 Correct 268 ms 88912 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 3 ms 23900 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 5 ms 24068 KB Output is correct
5 Incorrect 5 ms 24156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 3 ms 23900 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 5 ms 24068 KB Output is correct
5 Incorrect 5 ms 24156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23900 KB Output is correct
2 Correct 3 ms 23900 KB Output is correct
3 Correct 4 ms 23900 KB Output is correct
4 Correct 5 ms 24068 KB Output is correct
5 Incorrect 5 ms 24156 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 298 ms 93524 KB Output is correct
2 Correct 253 ms 67852 KB Output is correct
3 Correct 193 ms 50128 KB Output is correct
4 Correct 147 ms 53588 KB Output is correct
5 Correct 106 ms 62036 KB Output is correct
6 Correct 154 ms 56400 KB Output is correct
7 Correct 238 ms 76372 KB Output is correct
8 Correct 236 ms 50200 KB Output is correct
9 Correct 131 ms 58708 KB Output is correct
10 Correct 99 ms 62800 KB Output is correct
11 Correct 329 ms 100144 KB Output is correct
12 Correct 278 ms 84304 KB Output is correct
13 Correct 268 ms 88912 KB Output is correct
14 Correct 4 ms 23900 KB Output is correct
15 Correct 3 ms 23900 KB Output is correct
16 Correct 4 ms 23900 KB Output is correct
17 Correct 5 ms 24068 KB Output is correct
18 Incorrect 5 ms 24156 KB Output isn't correct
19 Halted 0 ms 0 KB -