oj.uz

답안 #994597

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
994597 2024-06-08T02:10:31 Z hmm789 Jobs (BOI24_jobs) C++14
11 / 100
 307 ms 248600 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);
	}
	assert(ans-s >= 0);
	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

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 226468 KB Output is correct
2 Correct 278 ms 226388 KB Output is correct
3 Correct 296 ms 245296 KB Output is correct
4 Correct 238 ms 240324 KB Output is correct
5 Correct 232 ms 247892 KB Output is correct
6 Correct 201 ms 222512 KB Output is correct
7 Correct 260 ms 226384 KB Output is correct
8 Correct 307 ms 245444 KB Output is correct
9 Correct 216 ms 246356 KB Output is correct
10 Correct 199 ms 248600 KB Output is correct
11 Correct 298 ms 226896 KB Output is correct
12 Correct 260 ms 225024 KB Output is correct
13 Correct 290 ms 225484 KB Output is correct

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 214100 KB Output is correct
2 Correct 92 ms 214096 KB Output is correct
3 Incorrect 91 ms 214236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 214100 KB Output is correct
2 Correct 92 ms 214096 KB Output is correct
3 Incorrect 91 ms 214236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 85 ms 214100 KB Output is correct
2 Correct 92 ms 214096 KB Output is correct
3 Incorrect 91 ms 214236 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 282 ms 226468 KB Output is correct
2 Correct 278 ms 226388 KB Output is correct
3 Correct 296 ms 245296 KB Output is correct
4 Correct 238 ms 240324 KB Output is correct
5 Correct 232 ms 247892 KB Output is correct
6 Correct 201 ms 222512 KB Output is correct
7 Correct 260 ms 226384 KB Output is correct
8 Correct 307 ms 245444 KB Output is correct
9 Correct 216 ms 246356 KB Output is correct
10 Correct 199 ms 248600 KB Output is correct
11 Correct 298 ms 226896 KB Output is correct
12 Correct 260 ms 225024 KB Output is correct
13 Correct 290 ms 225484 KB Output is correct
14 Correct 85 ms 214100 KB Output is correct
15 Correct 92 ms 214096 KB Output is correct
16 Incorrect 91 ms 214236 KB Output isn't correct
17 Halted 0 ms 0 KB -