Submission #655676

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
655676	2022-11-05T08:32:14 Z	lunchbox	Magic Tree (CEOI19_magictree)	C++17	100 / 100	287 ms	40328 KB

magictree

/*
 Magic Tree
 https://oj.uz/problem/view/CEOI19_magictree
*/
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;

int main() {
 ios::sync_with_stdio(0), cin.tie(0);
 int n, m, k; cin >> n >> m >> k;
 static int p[N];
 for (int i = 1; i < n; i++) cin >> p[i], p[i]--;
 static pair<int, int> e[N];
 while (m--) {
  int i, d, w; cin >> i >> d >> w, i--;
  e[i] = {d, w};
 }
 static map<int, long long> f[N];
 for (int i = n - 1; i > 0; i--) {
  if (e[i] != make_pair(0, 0)) {
   auto [d, w] = e[i];
   f[i][d] += w;
   auto it = f[i].upper_bound(d);
   while (w > 0 && it != f[i].end()) {
    long long u = min((long long) w, it->second);
    w -= u, it->second -= u, ++it;
   }
  }
  int j = p[i];
  if (f[i].size() > f[j].size()) swap(f[i], f[j]);
  for (auto [k, v] : f[i]) f[j][k] += v;
 }
 long long ans = 0;
 for (auto [k, v] : f[0]) ans += v;
 cout << ans << '\n';
 return 0;
}

Subtask #1
6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4932 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct

Subtask #2
3.0 / 3.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	45 ms	16900 KB	Output is correct
2	Correct	24 ms	9660 KB	Output is correct
3	Correct	135 ms	39820 KB	Output is correct
4	Correct	75 ms	17592 KB	Output is correct
5	Correct	118 ms	22860 KB	Output is correct

Subtask #3
11.0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	3 ms	5076 KB	Output is correct
4	Correct	56 ms	12080 KB	Output is correct
5	Correct	56 ms	11980 KB	Output is correct
6	Correct	287 ms	12048 KB	Output is correct

Subtask #4
12.0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	50 ms	12220 KB	Output is correct
2	Correct	42 ms	11140 KB	Output is correct
3	Correct	40 ms	9532 KB	Output is correct
4	Correct	37 ms	13512 KB	Output is correct
5	Correct	33 ms	8248 KB	Output is correct

Subtask #5
16.0 / 16.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4932 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	66 ms	16636 KB	Output is correct
11	Correct	51 ms	14800 KB	Output is correct
12	Correct	32 ms	8904 KB	Output is correct
13	Correct	37 ms	12860 KB	Output is correct
14	Correct	27 ms	7596 KB	Output is correct

Subtask #6
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	5588 KB	Output is correct
2	Correct	12 ms	6868 KB	Output is correct
3	Correct	11 ms	6868 KB	Output is correct
4	Correct	12 ms	6936 KB	Output is correct
5	Correct	9 ms	6484 KB	Output is correct
6	Correct	12 ms	6836 KB	Output is correct
7	Correct	12 ms	6844 KB	Output is correct

Subtask #7
22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4932 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	3 ms	5076 KB	Output is correct
11	Correct	3 ms	4948 KB	Output is correct
12	Correct	3 ms	5076 KB	Output is correct
13	Correct	56 ms	12080 KB	Output is correct
14	Correct	56 ms	11980 KB	Output is correct
15	Correct	287 ms	12048 KB	Output is correct
16	Correct	66 ms	16636 KB	Output is correct
17	Correct	51 ms	14800 KB	Output is correct
18	Correct	32 ms	8904 KB	Output is correct
19	Correct	37 ms	12860 KB	Output is correct
20	Correct	27 ms	7596 KB	Output is correct
21	Correct	20 ms	9820 KB	Output is correct
22	Correct	57 ms	19020 KB	Output is correct
23	Correct	71 ms	24080 KB	Output is correct
24	Correct	146 ms	40032 KB	Output is correct
25	Correct	71 ms	16884 KB	Output is correct
26	Correct	95 ms	19140 KB	Output is correct
27	Correct	91 ms	15224 KB	Output is correct

Subtask #8
17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	4948 KB	Output is correct
2	Correct	3 ms	4948 KB	Output is correct
3	Correct	2 ms	4948 KB	Output is correct
4	Correct	2 ms	4948 KB	Output is correct
5	Correct	3 ms	4932 KB	Output is correct
6	Correct	2 ms	4948 KB	Output is correct
7	Correct	3 ms	4948 KB	Output is correct
8	Correct	3 ms	4948 KB	Output is correct
9	Correct	3 ms	4948 KB	Output is correct
10	Correct	45 ms	16900 KB	Output is correct
11	Correct	24 ms	9660 KB	Output is correct
12	Correct	135 ms	39820 KB	Output is correct
13	Correct	75 ms	17592 KB	Output is correct
14	Correct	118 ms	22860 KB	Output is correct
15	Correct	3 ms	5076 KB	Output is correct
16	Correct	3 ms	4948 KB	Output is correct
17	Correct	3 ms	5076 KB	Output is correct
18	Correct	56 ms	12080 KB	Output is correct
19	Correct	56 ms	11980 KB	Output is correct
20	Correct	287 ms	12048 KB	Output is correct
21	Correct	50 ms	12220 KB	Output is correct
22	Correct	42 ms	11140 KB	Output is correct
23	Correct	40 ms	9532 KB	Output is correct
24	Correct	37 ms	13512 KB	Output is correct
25	Correct	33 ms	8248 KB	Output is correct
26	Correct	66 ms	16636 KB	Output is correct
27	Correct	51 ms	14800 KB	Output is correct
28	Correct	32 ms	8904 KB	Output is correct
29	Correct	37 ms	12860 KB	Output is correct
30	Correct	27 ms	7596 KB	Output is correct
31	Correct	5 ms	5588 KB	Output is correct
32	Correct	12 ms	6868 KB	Output is correct
33	Correct	11 ms	6868 KB	Output is correct
34	Correct	12 ms	6936 KB	Output is correct
35	Correct	9 ms	6484 KB	Output is correct
36	Correct	12 ms	6836 KB	Output is correct
37	Correct	12 ms	6844 KB	Output is correct
38	Correct	20 ms	9820 KB	Output is correct
39	Correct	57 ms	19020 KB	Output is correct
40	Correct	71 ms	24080 KB	Output is correct
41	Correct	146 ms	40032 KB	Output is correct
42	Correct	71 ms	16884 KB	Output is correct
43	Correct	95 ms	19140 KB	Output is correct
44	Correct	91 ms	15224 KB	Output is correct
45	Correct	20 ms	9932 KB	Output is correct
46	Correct	66 ms	19356 KB	Output is correct
47	Correct	75 ms	24320 KB	Output is correct
48	Correct	154 ms	40328 KB	Output is correct
49	Correct	66 ms	17596 KB	Output is correct
50	Correct	104 ms	19976 KB	Output is correct
51	Correct	113 ms	15880 KB	Output is correct

Submission #655676

Compilation message