Submission #994937

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
994937	2024-06-08T08:41:18 Z	emptypringlescan	Jobs (BOI24_jobs)	C++17	11 / 100	248 ms	59220 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-i.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;
}

Subtask #1

11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	39764 KB	Output is correct
2	Correct	180 ms	39504 KB	Output is correct
3	Correct	165 ms	38608 KB	Output is correct
4	Correct	137 ms	49748 KB	Output is correct
5	Correct	98 ms	58516 KB	Output is correct
6	Correct	119 ms	30800 KB	Output is correct
7	Correct	202 ms	40396 KB	Output is correct
8	Correct	154 ms	38708 KB	Output is correct
9	Correct	114 ms	55756 KB	Output is correct
10	Correct	92 ms	59220 KB	Output is correct
11	Correct	248 ms	42576 KB	Output is correct
12	Correct	182 ms	38740 KB	Output is correct
13	Correct	206 ms	36432 KB	Output is correct

Subtask #2

0 / 14.0

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

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	245 ms	39764 KB	Output is correct
2	Correct	180 ms	39504 KB	Output is correct
3	Correct	165 ms	38608 KB	Output is correct
4	Correct	137 ms	49748 KB	Output is correct
5	Correct	98 ms	58516 KB	Output is correct
6	Correct	119 ms	30800 KB	Output is correct
7	Correct	202 ms	40396 KB	Output is correct
8	Correct	154 ms	38708 KB	Output is correct
9	Correct	114 ms	55756 KB	Output is correct
10	Correct	92 ms	59220 KB	Output is correct
11	Correct	248 ms	42576 KB	Output is correct
12	Correct	182 ms	38740 KB	Output is correct
13	Correct	206 ms	36432 KB	Output is correct
14	Correct	4 ms	21336 KB	Output is correct
15	Correct	3 ms	21336 KB	Output is correct
16	Correct	4 ms	21596 KB	Output is correct
17	Correct	4 ms	21592 KB	Output is correct
18	Incorrect	4 ms	21852 KB	Output isn't correct
19	Halted	0 ms	0 KB	-