#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> adj[300001];
int a[300001];
deque<int> v[300001];
int mn[300001], sm[300001];
void dfs(int x, int p) {
v[x].push_back(a[x]);
sm[x] = mn[x] = a[x];
vector<tuple<int, int, deque<int>>> vec;
for(int i : adj[x]) if(i != p) {
dfs(i, x);
vec.push_back({-mn[i], sm[i], v[i]});
}
sort(vec.begin(), vec.end());
for(auto [m, s, v2] : vec) {
m = -m;
if(v[x].size() < v2.size()) {
swap(v[x], v2);
while(v2.size()) {
v[x].push_front(v2.back());
v2.pop_back();
}
} else {
while(v2.size()) {
v[x].push_back(v2.front());
v2.pop_front();
}
}
mn[x] = min(mn[x], sm[x]+m);
sm[x] += s;
}
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, -1);
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, long long int)':
Main.cpp:20:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
20 | for(auto [m, s, v2] : vec) {
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
563 ms |
446152 KB |
Output is correct |
2 |
Correct |
423 ms |
290164 KB |
Output is correct |
3 |
Correct |
608 ms |
347168 KB |
Output is correct |
4 |
Runtime error |
548 ms |
1048576 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
214096 KB |
Output is correct |
2 |
Correct |
93 ms |
214076 KB |
Output is correct |
3 |
Incorrect |
92 ms |
214136 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
214096 KB |
Output is correct |
2 |
Correct |
93 ms |
214076 KB |
Output is correct |
3 |
Incorrect |
92 ms |
214136 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
81 ms |
214096 KB |
Output is correct |
2 |
Correct |
93 ms |
214076 KB |
Output is correct |
3 |
Incorrect |
92 ms |
214136 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
563 ms |
446152 KB |
Output is correct |
2 |
Correct |
423 ms |
290164 KB |
Output is correct |
3 |
Correct |
608 ms |
347168 KB |
Output is correct |
4 |
Runtime error |
548 ms |
1048576 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |