Submission #994961

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
994961	2024-06-08T08:55:11 Z	emptypringlescan	Jobs (BOI24_jobs)	C++17	11 / 100	268 ms	59216 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(0ll,s[i.first].begin()->first-ins.first);
				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;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	225 ms	39768 KB	Output is correct
2	Correct	183 ms	39480 KB	Output is correct
3	Correct	166 ms	38624 KB	Output is correct
4	Correct	118 ms	49656 KB	Output is correct
5	Correct	96 ms	58452 KB	Output is correct
6	Correct	126 ms	30980 KB	Output is correct
7	Correct	202 ms	40528 KB	Output is correct
8	Correct	143 ms	38604 KB	Output is correct
9	Correct	100 ms	55892 KB	Output is correct
10	Correct	90 ms	59216 KB	Output is correct
11	Correct	239 ms	42660 KB	Output is correct
12	Correct	201 ms	38596 KB	Output is correct
13	Correct	268 ms	36348 KB	Output is correct

Subtask #2

0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	21340 KB	Output is correct
2	Correct	4 ms	21596 KB	Output is correct
3	Correct	4 ms	21340 KB	Output is correct
4	Correct	5 ms	21596 KB	Output is correct
5	Correct	4 ms	21852 KB	Output is correct
6	Correct	4 ms	21852 KB	Output is correct
7	Correct	4 ms	21592 KB	Output is correct
8	Correct	4 ms	21612 KB	Output is correct
9	Correct	5 ms	21592 KB	Output is correct
10	Incorrect	4 ms	21680 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #3

0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	21340 KB	Output is correct
2	Correct	4 ms	21596 KB	Output is correct
3	Correct	4 ms	21340 KB	Output is correct
4	Correct	5 ms	21596 KB	Output is correct
5	Correct	4 ms	21852 KB	Output is correct
6	Correct	4 ms	21852 KB	Output is correct
7	Correct	4 ms	21592 KB	Output is correct
8	Correct	4 ms	21612 KB	Output is correct
9	Correct	5 ms	21592 KB	Output is correct
10	Incorrect	4 ms	21680 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #4

0 / 29.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	21340 KB	Output is correct
2	Correct	4 ms	21596 KB	Output is correct
3	Correct	4 ms	21340 KB	Output is correct
4	Correct	5 ms	21596 KB	Output is correct
5	Correct	4 ms	21852 KB	Output is correct
6	Correct	4 ms	21852 KB	Output is correct
7	Correct	4 ms	21592 KB	Output is correct
8	Correct	4 ms	21612 KB	Output is correct
9	Correct	5 ms	21592 KB	Output is correct
10	Incorrect	4 ms	21680 KB	Output isn't correct
11	Halted	0 ms	0 KB	-

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	225 ms	39768 KB	Output is correct
2	Correct	183 ms	39480 KB	Output is correct
3	Correct	166 ms	38624 KB	Output is correct
4	Correct	118 ms	49656 KB	Output is correct
5	Correct	96 ms	58452 KB	Output is correct
6	Correct	126 ms	30980 KB	Output is correct
7	Correct	202 ms	40528 KB	Output is correct
8	Correct	143 ms	38604 KB	Output is correct
9	Correct	100 ms	55892 KB	Output is correct
10	Correct	90 ms	59216 KB	Output is correct
11	Correct	239 ms	42660 KB	Output is correct
12	Correct	201 ms	38596 KB	Output is correct
13	Correct	268 ms	36348 KB	Output is correct
14	Correct	4 ms	21340 KB	Output is correct
15	Correct	4 ms	21596 KB	Output is correct
16	Correct	4 ms	21340 KB	Output is correct
17	Correct	5 ms	21596 KB	Output is correct
18	Correct	4 ms	21852 KB	Output is correct
19	Correct	4 ms	21852 KB	Output is correct
20	Correct	4 ms	21592 KB	Output is correct
21	Correct	4 ms	21612 KB	Output is correct
22	Correct	5 ms	21592 KB	Output is correct
23	Incorrect	4 ms	21680 KB	Output isn't correct
24	Halted	0 ms	0 KB	-