# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
706470 | 2023-03-06T16:39:25 Z | LittleCube | Magic Tree (CEOI19_magictree) | C++14 | 187 ms | 34060 KB |
#include <bits/stdc++.h> #define ll long long using namespace std; int n, m, k, p[100005], d[100005], sz[100005]; ll w[100005]; vector<int> E[100005]; map<int, ll> mp[100005]; void dfs(int u) { sz[u] = 1; for (int v : E[u]) { dfs(v); sz[u] += sz[v]; } sort(E[u].begin(), E[u].end(), [&](int i, int j) { return sz[i] > sz[j]; }); for (int i = 0; i < E[u].size(); i++) { int v = E[u][i]; if (i == 0) mp[u].swap(mp[v]); else { for(auto [p, val] : mp[v]) mp[u][p] += val; mp[v].clear(); } } if(w[u]) { ll r = w[u]; mp[u][d[u]] += w[u]; auto iter = mp[u].upper_bound(d[u]); while(r > 0 && iter != mp[u].end()) { ll cur = iter->second; if(r >= cur) iter = mp[u].erase(iter); else iter->second -= r; r -= cur; } } } signed main() { cin >> n >> m >> k; for (int i = 2; i <= n; i++) { cin >> p[i]; E[p[i]].emplace_back(i); } for (int i = 1; i <= m; i++) { int v; cin >> v; cin >> d[v] >> w[v]; } dfs(1); ll ans = 0; for(auto [p, v] : mp[1]) ans += v; cout << ans << '\n'; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7356 KB | Output is correct |
3 | Correct | 4 ms | 7252 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 4 ms | 7348 KB | Output is correct |
6 | Correct | 4 ms | 7252 KB | Output is correct |
7 | Correct | 4 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7252 KB | Output is correct |
9 | Correct | 4 ms | 7252 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 87 ms | 13836 KB | Output is correct |
2 | Correct | 70 ms | 19808 KB | Output is correct |
3 | Correct | 177 ms | 18292 KB | Output is correct |
4 | Correct | 141 ms | 17428 KB | Output is correct |
5 | Correct | 152 ms | 17528 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 7508 KB | Output is correct |
2 | Correct | 5 ms | 7508 KB | Output is correct |
3 | Correct | 5 ms | 7508 KB | Output is correct |
4 | Correct | 112 ms | 29872 KB | Output is correct |
5 | Correct | 139 ms | 34060 KB | Output is correct |
6 | Correct | 122 ms | 29904 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 119 ms | 12928 KB | Output is correct |
2 | Correct | 120 ms | 12932 KB | Output is correct |
3 | Correct | 123 ms | 20172 KB | Output is correct |
4 | Correct | 97 ms | 16956 KB | Output is correct |
5 | Correct | 116 ms | 30144 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7356 KB | Output is correct |
3 | Correct | 4 ms | 7252 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 4 ms | 7348 KB | Output is correct |
6 | Correct | 4 ms | 7252 KB | Output is correct |
7 | Correct | 4 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7252 KB | Output is correct |
9 | Correct | 4 ms | 7252 KB | Output is correct |
10 | Correct | 109 ms | 12388 KB | Output is correct |
11 | Correct | 106 ms | 12336 KB | Output is correct |
12 | Correct | 96 ms | 19448 KB | Output is correct |
13 | Correct | 79 ms | 16432 KB | Output is correct |
14 | Correct | 96 ms | 29564 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 12 ms | 8164 KB | Output is correct |
2 | Correct | 47 ms | 11428 KB | Output is correct |
3 | Correct | 47 ms | 11408 KB | Output is correct |
4 | Correct | 49 ms | 11460 KB | Output is correct |
5 | Correct | 23 ms | 10024 KB | Output is correct |
6 | Correct | 54 ms | 14348 KB | Output is correct |
7 | Correct | 49 ms | 18668 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7356 KB | Output is correct |
3 | Correct | 4 ms | 7252 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 4 ms | 7348 KB | Output is correct |
6 | Correct | 4 ms | 7252 KB | Output is correct |
7 | Correct | 4 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7252 KB | Output is correct |
9 | Correct | 4 ms | 7252 KB | Output is correct |
10 | Correct | 5 ms | 7508 KB | Output is correct |
11 | Correct | 5 ms | 7508 KB | Output is correct |
12 | Correct | 5 ms | 7508 KB | Output is correct |
13 | Correct | 112 ms | 29872 KB | Output is correct |
14 | Correct | 139 ms | 34060 KB | Output is correct |
15 | Correct | 122 ms | 29904 KB | Output is correct |
16 | Correct | 109 ms | 12388 KB | Output is correct |
17 | Correct | 106 ms | 12336 KB | Output is correct |
18 | Correct | 96 ms | 19448 KB | Output is correct |
19 | Correct | 79 ms | 16432 KB | Output is correct |
20 | Correct | 96 ms | 29564 KB | Output is correct |
21 | Correct | 30 ms | 8616 KB | Output is correct |
22 | Correct | 99 ms | 12472 KB | Output is correct |
23 | Correct | 116 ms | 14532 KB | Output is correct |
24 | Correct | 158 ms | 16624 KB | Output is correct |
25 | Correct | 107 ms | 16704 KB | Output is correct |
26 | Correct | 136 ms | 19440 KB | Output is correct |
27 | Correct | 129 ms | 21324 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 7252 KB | Output is correct |
2 | Correct | 5 ms | 7356 KB | Output is correct |
3 | Correct | 4 ms | 7252 KB | Output is correct |
4 | Correct | 4 ms | 7252 KB | Output is correct |
5 | Correct | 4 ms | 7348 KB | Output is correct |
6 | Correct | 4 ms | 7252 KB | Output is correct |
7 | Correct | 4 ms | 7252 KB | Output is correct |
8 | Correct | 4 ms | 7252 KB | Output is correct |
9 | Correct | 4 ms | 7252 KB | Output is correct |
10 | Correct | 87 ms | 13836 KB | Output is correct |
11 | Correct | 70 ms | 19808 KB | Output is correct |
12 | Correct | 177 ms | 18292 KB | Output is correct |
13 | Correct | 141 ms | 17428 KB | Output is correct |
14 | Correct | 152 ms | 17528 KB | Output is correct |
15 | Correct | 5 ms | 7508 KB | Output is correct |
16 | Correct | 5 ms | 7508 KB | Output is correct |
17 | Correct | 5 ms | 7508 KB | Output is correct |
18 | Correct | 112 ms | 29872 KB | Output is correct |
19 | Correct | 139 ms | 34060 KB | Output is correct |
20 | Correct | 122 ms | 29904 KB | Output is correct |
21 | Correct | 119 ms | 12928 KB | Output is correct |
22 | Correct | 120 ms | 12932 KB | Output is correct |
23 | Correct | 123 ms | 20172 KB | Output is correct |
24 | Correct | 97 ms | 16956 KB | Output is correct |
25 | Correct | 116 ms | 30144 KB | Output is correct |
26 | Correct | 109 ms | 12388 KB | Output is correct |
27 | Correct | 106 ms | 12336 KB | Output is correct |
28 | Correct | 96 ms | 19448 KB | Output is correct |
29 | Correct | 79 ms | 16432 KB | Output is correct |
30 | Correct | 96 ms | 29564 KB | Output is correct |
31 | Correct | 12 ms | 8164 KB | Output is correct |
32 | Correct | 47 ms | 11428 KB | Output is correct |
33 | Correct | 47 ms | 11408 KB | Output is correct |
34 | Correct | 49 ms | 11460 KB | Output is correct |
35 | Correct | 23 ms | 10024 KB | Output is correct |
36 | Correct | 54 ms | 14348 KB | Output is correct |
37 | Correct | 49 ms | 18668 KB | Output is correct |
38 | Correct | 30 ms | 8616 KB | Output is correct |
39 | Correct | 99 ms | 12472 KB | Output is correct |
40 | Correct | 116 ms | 14532 KB | Output is correct |
41 | Correct | 158 ms | 16624 KB | Output is correct |
42 | Correct | 107 ms | 16704 KB | Output is correct |
43 | Correct | 136 ms | 19440 KB | Output is correct |
44 | Correct | 129 ms | 21324 KB | Output is correct |
45 | Correct | 33 ms | 8920 KB | Output is correct |
46 | Correct | 118 ms | 12800 KB | Output is correct |
47 | Correct | 118 ms | 14732 KB | Output is correct |
48 | Correct | 187 ms | 17472 KB | Output is correct |
49 | Correct | 134 ms | 17344 KB | Output is correct |
50 | Correct | 158 ms | 20428 KB | Output is correct |
51 | Correct | 149 ms | 22260 KB | Output is correct |