oj.uz

Submission #994594

# Submission time Handle Problem Language Result Execution time Memory
994594 2024-06-08T02:09:22 Z hmm789 Jobs (BOI24_jobs) C++14
11 / 100
 308 ms 248400 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];

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});
	}
	sort(vec.begin(), vec.end());
	for(auto [m, idx] : vec) {
		m = -m;
		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);
	for(int i : v[0]) {
		cur += i;
		if(cur < 0) break;
		ans = max(ans, cur);
	}
	cout << ans-s;
}

Compilation message

Main.cpp: In function 'void dfs(long long int)':
Main.cpp:21:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   21 |  for(auto [m, idx] : vec) {
      |           ^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 305 ms 226648 KB Output is correct
2 Correct 287 ms 226388 KB Output is correct
3 Correct 301 ms 245456 KB Output is correct
4 Correct 232 ms 240468 KB Output is correct
5 Correct 226 ms 248008 KB Output is correct
6 Correct 200 ms 222392 KB Output is correct
7 Correct 307 ms 226384 KB Output is correct
8 Correct 308 ms 245296 KB Output is correct
9 Correct 213 ms 246356 KB Output is correct
10 Correct 226 ms 248400 KB Output is correct
11 Correct 299 ms 226796 KB Output is correct
12 Correct 276 ms 225188 KB Output is correct
13 Correct 279 ms 225584 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 214048 KB Output is correct
2 Correct 83 ms 214096 KB Output is correct
3 Incorrect 83 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 86 ms 214048 KB Output is correct
2 Correct 83 ms 214096 KB Output is correct
3 Incorrect 83 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 86 ms 214048 KB Output is correct
2 Correct 83 ms 214096 KB Output is correct
3 Incorrect 83 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 305 ms 226648 KB Output is correct
2 Correct 287 ms 226388 KB Output is correct
3 Correct 301 ms 245456 KB Output is correct
4 Correct 232 ms 240468 KB Output is correct
5 Correct 226 ms 248008 KB Output is correct
6 Correct 200 ms 222392 KB Output is correct
7 Correct 307 ms 226384 KB Output is correct
8 Correct 308 ms 245296 KB Output is correct
9 Correct 213 ms 246356 KB Output is correct
10 Correct 226 ms 248400 KB Output is correct
11 Correct 299 ms 226796 KB Output is correct
12 Correct 276 ms 225188 KB Output is correct
13 Correct 279 ms 225584 KB Output is correct
14 Correct 86 ms 214048 KB Output is correct
15 Correct 83 ms 214096 KB Output is correct
16 Incorrect 83 ms 214196 KB Output isn't correct
17 Halted 0 ms 0 KB -