Submission #994977

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
994977	2024-06-08T09:07:45 Z	emptypringlescan	Jobs (BOI24_jobs)	C++17	11 / 100	239 ms	59016 KB

Main

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,long long> > adj[300005];
multiset<pair<long long,long long> > s[300005];
void greed(int x){
	for(auto i:adj[x]){
		greed(i.first);
		if(i.second>=0){
			s[i.first].insert({0,i.second});
		}
		else{
			pair<long long,long long> ins={-i.second,i.second};
			while(ins.second<0||(!s[i.first].empty()&&s[i.first].begin()->first<=ins.first)){
				if(s[i.first].empty()) break;
				ins.second+=s[i.first].begin()->second;
				ins.first=max(ins.first,s[i.first].begin()->first-ins.second);
				s[i.first].erase(s[i.first].begin());
			}
			if(ins.second>0) s[i.first].insert(ins);
			
		}
		if(s[i.first].size()>s[x].size()) swap(s[i.first],s[x]);
		for(auto j:s[i.first]) s[x].insert(j);
		s[i.first].clear();
	}
	//cout << x << ":\n";
	//for(auto i:s[x]) cout << i.first << ' ' << i.second << '\n';
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	long long n,m;
	cin >> n >> m;
	for(int i=1; i<=n; i++){
		long long a,b;
		cin >> a >> b;
		adj[b].push_back({i,a});
	}
	greed(0);
	long long org=m;
	for(auto i:s[0]){
		if(m>=i.first) m+=i.second;
	}
	cout << m-org;
}
/*7 0
-100 0
-20 1
30 2
101 1
100 0
-101 5
1000 6*/

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	39644 KB	Output is correct
2	Correct	188 ms	39504 KB	Output is correct
3	Correct	153 ms	38692 KB	Output is correct
4	Correct	113 ms	49752 KB	Output is correct
5	Correct	95 ms	58412 KB	Output is correct
6	Correct	114 ms	30804 KB	Output is correct
7	Correct	239 ms	40532 KB	Output is correct
8	Correct	153 ms	38608 KB	Output is correct
9	Correct	107 ms	55808 KB	Output is correct
10	Correct	102 ms	59016 KB	Output is correct
11	Correct	238 ms	42580 KB	Output is correct
12	Correct	214 ms	38628 KB	Output is correct
13	Correct	224 ms	36352 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	21336 KB	Output is correct
2	Correct	3 ms	21340 KB	Output is correct
3	Correct	3 ms	21340 KB	Output is correct
4	Correct	5 ms	21592 KB	Output is correct
5	Correct	5 ms	21852 KB	Output is correct
6	Correct	6 ms	22008 KB	Output is correct
7	Correct	4 ms	21596 KB	Output is correct
8	Correct	4 ms	21596 KB	Output is correct
9	Correct	4 ms	21596 KB	Output is correct
10	Incorrect	4 ms	21596 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	21336 KB	Output is correct
2	Correct	3 ms	21340 KB	Output is correct
3	Correct	3 ms	21340 KB	Output is correct
4	Correct	5 ms	21592 KB	Output is correct
5	Correct	5 ms	21852 KB	Output is correct
6	Correct	6 ms	22008 KB	Output is correct
7	Correct	4 ms	21596 KB	Output is correct
8	Correct	4 ms	21596 KB	Output is correct
9	Correct	4 ms	21596 KB	Output is correct
10	Incorrect	4 ms	21596 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	21336 KB	Output is correct
2	Correct	3 ms	21340 KB	Output is correct
3	Correct	3 ms	21340 KB	Output is correct
4	Correct	5 ms	21592 KB	Output is correct
5	Correct	5 ms	21852 KB	Output is correct
6	Correct	6 ms	22008 KB	Output is correct
7	Correct	4 ms	21596 KB	Output is correct
8	Correct	4 ms	21596 KB	Output is correct
9	Correct	4 ms	21596 KB	Output is correct
10	Incorrect	4 ms	21596 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	218 ms	39644 KB	Output is correct
2	Correct	188 ms	39504 KB	Output is correct
3	Correct	153 ms	38692 KB	Output is correct
4	Correct	113 ms	49752 KB	Output is correct
5	Correct	95 ms	58412 KB	Output is correct
6	Correct	114 ms	30804 KB	Output is correct
7	Correct	239 ms	40532 KB	Output is correct
8	Correct	153 ms	38608 KB	Output is correct
9	Correct	107 ms	55808 KB	Output is correct
10	Correct	102 ms	59016 KB	Output is correct
11	Correct	238 ms	42580 KB	Output is correct
12	Correct	214 ms	38628 KB	Output is correct
13	Correct	224 ms	36352 KB	Output is correct
14	Correct	3 ms	21336 KB	Output is correct
15	Correct	3 ms	21340 KB	Output is correct
16	Correct	3 ms	21340 KB	Output is correct
17	Correct	5 ms	21592 KB	Output is correct
18	Correct	5 ms	21852 KB	Output is correct
19	Correct	6 ms	22008 KB	Output is correct
20	Correct	4 ms	21596 KB	Output is correct
21	Correct	4 ms	21596 KB	Output is correct
22	Correct	4 ms	21596 KB	Output is correct
23	Incorrect	4 ms	21596 KB	Output isn't correct
24	Halted	0 ms	0 KB	-