#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int N, M, K, res = 0;
cin >> N >> M >> K;
vector<int> g[N];
int d[N] {}, w[N] {};
for(int i = 1; i < N; i++) {
int p; cin >> p;
g[p-1].push_back(i);
}
while(M--) {
int u;
cin >> u >> d[u-1] >> w[u-1];
}
map<int, int> dp[N];
for(int u = N; --u >= 0; ) {
int h = 0;
for(int v : g[u])
if(size(dp[v]) > size(dp[h])) h = v;
dp[h].swap(dp[u]);
for(int v : g[u]) if(v != h)
for(auto &[i, j] : dp[v])
dp[u][i] += j;
dp[u][d[u]] += w[u];
auto f = dp[u].upper_bound(d[u]);
while(f != end(dp[u]) && ((*f).second -= w[u]) < 0)
w[u] = -(*f).second, f = dp[u].erase(f);
}
for(auto &[i, j] : dp[0]) res += j;
cout << res;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
216 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
55 ms |
22000 KB |
Output is correct |
2 |
Correct |
35 ms |
15468 KB |
Output is correct |
3 |
Correct |
112 ms |
37164 KB |
Output is correct |
4 |
Correct |
62 ms |
21780 KB |
Output is correct |
5 |
Correct |
84 ms |
21864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
1 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
460 KB |
Output is correct |
4 |
Correct |
42 ms |
13892 KB |
Output is correct |
5 |
Correct |
61 ms |
17812 KB |
Output is correct |
6 |
Correct |
56 ms |
13992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
56 ms |
17220 KB |
Output is correct |
2 |
Correct |
60 ms |
16456 KB |
Output is correct |
3 |
Correct |
47 ms |
14832 KB |
Output is correct |
4 |
Correct |
40 ms |
17660 KB |
Output is correct |
5 |
Correct |
42 ms |
14048 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
216 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
65 ms |
20516 KB |
Output is correct |
11 |
Correct |
71 ms |
19400 KB |
Output is correct |
12 |
Correct |
45 ms |
14160 KB |
Output is correct |
13 |
Correct |
35 ms |
17024 KB |
Output is correct |
14 |
Correct |
47 ms |
13476 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
3296 KB |
Output is correct |
2 |
Correct |
31 ms |
14632 KB |
Output is correct |
3 |
Correct |
30 ms |
14560 KB |
Output is correct |
4 |
Correct |
33 ms |
14908 KB |
Output is correct |
5 |
Correct |
19 ms |
16196 KB |
Output is correct |
6 |
Correct |
29 ms |
14952 KB |
Output is correct |
7 |
Correct |
24 ms |
13252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
216 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
1 ms |
332 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
460 KB |
Output is correct |
13 |
Correct |
42 ms |
13892 KB |
Output is correct |
14 |
Correct |
61 ms |
17812 KB |
Output is correct |
15 |
Correct |
56 ms |
13992 KB |
Output is correct |
16 |
Correct |
65 ms |
20516 KB |
Output is correct |
17 |
Correct |
71 ms |
19400 KB |
Output is correct |
18 |
Correct |
45 ms |
14160 KB |
Output is correct |
19 |
Correct |
35 ms |
17024 KB |
Output is correct |
20 |
Correct |
47 ms |
13476 KB |
Output is correct |
21 |
Correct |
17 ms |
6092 KB |
Output is correct |
22 |
Correct |
68 ms |
23412 KB |
Output is correct |
23 |
Correct |
86 ms |
27772 KB |
Output is correct |
24 |
Correct |
149 ms |
37624 KB |
Output is correct |
25 |
Correct |
61 ms |
21068 KB |
Output is correct |
26 |
Correct |
83 ms |
20988 KB |
Output is correct |
27 |
Correct |
72 ms |
16860 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
312 KB |
Output is correct |
2 |
Correct |
0 ms |
308 KB |
Output is correct |
3 |
Correct |
1 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
216 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
312 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
1 ms |
204 KB |
Output is correct |
10 |
Correct |
55 ms |
22000 KB |
Output is correct |
11 |
Correct |
35 ms |
15468 KB |
Output is correct |
12 |
Correct |
112 ms |
37164 KB |
Output is correct |
13 |
Correct |
62 ms |
21780 KB |
Output is correct |
14 |
Correct |
84 ms |
21864 KB |
Output is correct |
15 |
Correct |
1 ms |
332 KB |
Output is correct |
16 |
Correct |
1 ms |
332 KB |
Output is correct |
17 |
Correct |
1 ms |
460 KB |
Output is correct |
18 |
Correct |
42 ms |
13892 KB |
Output is correct |
19 |
Correct |
61 ms |
17812 KB |
Output is correct |
20 |
Correct |
56 ms |
13992 KB |
Output is correct |
21 |
Correct |
56 ms |
17220 KB |
Output is correct |
22 |
Correct |
60 ms |
16456 KB |
Output is correct |
23 |
Correct |
47 ms |
14832 KB |
Output is correct |
24 |
Correct |
40 ms |
17660 KB |
Output is correct |
25 |
Correct |
42 ms |
14048 KB |
Output is correct |
26 |
Correct |
65 ms |
20516 KB |
Output is correct |
27 |
Correct |
71 ms |
19400 KB |
Output is correct |
28 |
Correct |
45 ms |
14160 KB |
Output is correct |
29 |
Correct |
35 ms |
17024 KB |
Output is correct |
30 |
Correct |
47 ms |
13476 KB |
Output is correct |
31 |
Correct |
6 ms |
3296 KB |
Output is correct |
32 |
Correct |
31 ms |
14632 KB |
Output is correct |
33 |
Correct |
30 ms |
14560 KB |
Output is correct |
34 |
Correct |
33 ms |
14908 KB |
Output is correct |
35 |
Correct |
19 ms |
16196 KB |
Output is correct |
36 |
Correct |
29 ms |
14952 KB |
Output is correct |
37 |
Correct |
24 ms |
13252 KB |
Output is correct |
38 |
Correct |
17 ms |
6092 KB |
Output is correct |
39 |
Correct |
68 ms |
23412 KB |
Output is correct |
40 |
Correct |
86 ms |
27772 KB |
Output is correct |
41 |
Correct |
149 ms |
37624 KB |
Output is correct |
42 |
Correct |
61 ms |
21068 KB |
Output is correct |
43 |
Correct |
83 ms |
20988 KB |
Output is correct |
44 |
Correct |
72 ms |
16860 KB |
Output is correct |
45 |
Correct |
24 ms |
5828 KB |
Output is correct |
46 |
Correct |
74 ms |
22852 KB |
Output is correct |
47 |
Correct |
79 ms |
26276 KB |
Output is correct |
48 |
Correct |
119 ms |
34776 KB |
Output is correct |
49 |
Correct |
77 ms |
21760 KB |
Output is correct |
50 |
Correct |
90 ms |
20964 KB |
Output is correct |
51 |
Correct |
80 ms |
16860 KB |
Output is correct |