oj.uz

Submission #994626

# Submission time Handle Problem Language Result Execution time Memory
994626 2024-06-08T02:41:22 Z hmm789 Jobs (BOI24_jobs) C++14
11 / 100
 343 ms 248432 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long 

vector<int> adj[300005];
int a[300005];

deque<int> v[300005];
int mn[300005], sm[300005];
vector<int> ed;

void dfs(int x) {
	v[x].push_back(a[x]);
	sm[x] = a[x];
	mn[x] = min(a[x], 0LL);
	vector<pair<int, int>> vec;
	for(int i : adj[x]) {
		dfs(i);
		vec.push_back({-mn[i],i});
	}
	if(x == 0) ed.push_back(0);
	sort(vec.begin(), vec.end());
	for(auto [m, idx] : vec) {
		m = -m;
		if(x == 0) ed.push_back(ed.back()+v[idx].size());
		if(v[x].size() < v[idx].size()) {
			swap(v[x], v[idx]);
			while(v[idx].size()) {
				v[x].push_front(v[idx].back());
				v[idx].pop_back();
			}
		} else {
			while(v[idx].size()) {
				v[x].push_back(v[idx].front());
				v[idx].pop_front();
			}
		}
		mn[x] = min(mn[x], sm[x]+m);
		sm[x] += sm[idx];
	}
	if(sm[x] <= 0) {
		v[x].clear();
		sm[x] = mn[x] = 0;
	}
}

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, s, x, ans = 0, cur = 0;
	cin >> n >> s;
	a[0] = s;
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> x;
		adj[x].push_back(i);
	}
	dfs(0);
	int idx = 0;
	for(int i = 0; i < v[0].size(); i++) {
		cur += v[0][i];
		while(idx < ed.size() && ed[idx] < i) idx++;
		if(cur < 0) {
			cur = ans;
			if(idx < ed.size()) i = ed[idx];
			else break;
		}
		ans = max(ans, cur);
	}
	cout << ans-s;
}

Compilation message

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:23:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   23 |  for(auto [m, idx] : vec) {
      |           ^
Main.cpp: In function 'int32_t main()':
Main.cpp:59:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for(int i = 0; i < v[0].size(); i++) {
      |                 ~~^~~~~~~~~~~~~
Main.cpp:61:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   while(idx < ed.size() && ed[idx] < i) idx++;
      |         ~~~~^~~~~~~~~~~
Main.cpp:64:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |    if(idx < ed.size()) i = ed[idx];
      |       ~~~~^~~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 226644 KB Output is correct
2 Correct 300 ms 226384 KB Output is correct
3 Correct 329 ms 246976 KB Output is correct
4 Correct 253 ms 240392 KB Output is correct
5 Correct 246 ms 247892 KB Output is correct
6 Correct 232 ms 222548 KB Output is correct
7 Correct 325 ms 226296 KB Output is correct
8 Correct 343 ms 246976 KB Output is correct
9 Correct 248 ms 246244 KB Output is correct
10 Correct 258 ms 248432 KB Output is correct
11 Correct 339 ms 226644 KB Output is correct
12 Correct 289 ms 224848 KB Output is correct
13 Correct 304 ms 225360 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 214096 KB Output is correct
2 Correct 103 ms 214020 KB Output is correct
3 Incorrect 107 ms 214196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 214096 KB Output is correct
2 Correct 103 ms 214020 KB Output is correct
3 Incorrect 107 ms 214196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 214096 KB Output is correct
2 Correct 103 ms 214020 KB Output is correct
3 Incorrect 107 ms 214196 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 310 ms 226644 KB Output is correct
2 Correct 300 ms 226384 KB Output is correct
3 Correct 329 ms 246976 KB Output is correct
4 Correct 253 ms 240392 KB Output is correct
5 Correct 246 ms 247892 KB Output is correct
6 Correct 232 ms 222548 KB Output is correct
7 Correct 325 ms 226296 KB Output is correct
8 Correct 343 ms 246976 KB Output is correct
9 Correct 248 ms 246244 KB Output is correct
10 Correct 258 ms 248432 KB Output is correct
11 Correct 339 ms 226644 KB Output is correct
12 Correct 289 ms 224848 KB Output is correct
13 Correct 304 ms 225360 KB Output is correct
14 Correct 102 ms 214096 KB Output is correct
15 Correct 103 ms 214020 KB Output is correct
16 Incorrect 107 ms 214196 KB Output isn't correct
17 Halted 0 ms 0 KB -