# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
347200 | 2021-01-12T11:05:34 Z | parsabahrami | Cat in a tree (BOI17_catinatree) | C++17 | 110 ms | 14572 KB |
// Call my Name and Save me from The Dark #include <bits/stdc++.h> using namespace std; typedef long long int ll; typedef pair<int, int> pii; #define SZ(x) (int) x.size() #define F first #define S second const int N = 2e5 + 10, MOD = 1e9 + 7; int mx[N], dp[N], n, D; vector<int> adj[N]; void DFS(int v) { if (!SZ(adj[v])) { dp[v] = 1, mx[v] = 0; return; } for (int u : adj[v]) DFS(u); sort(adj[v].begin(), adj[v].end(), [&](int u, int w) { return mx[u] > mx[w]; }); int M = MOD, res = 0; for (int u : adj[v]) { if (mx[u] + M + 2 >= D) { res += dp[u], M = mx[u]; } else res += dp[u] - 1; } if (M >= D - 1) { M = -1, res++; } dp[v] = res, mx[v] = M + 1; } int main() { scanf("%d%d", &n, &D); for (int i = 1; i < n; i++) { int p; scanf("%d", &p); adj[p].push_back(i); } DFS(0); printf("%d\n", dp[0]); return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 4 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 5 ms | 4992 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Correct | 4 ms | 4972 KB | Output is correct |
7 | Correct | 3 ms | 4972 KB | Output is correct |
8 | Correct | 4 ms | 4972 KB | Output is correct |
9 | Correct | 3 ms | 4972 KB | Output is correct |
10 | Correct | 4 ms | 4972 KB | Output is correct |
11 | Correct | 4 ms | 4972 KB | Output is correct |
12 | Correct | 3 ms | 4972 KB | Output is correct |
13 | Correct | 4 ms | 4972 KB | Output is correct |
14 | Correct | 4 ms | 4972 KB | Output is correct |
15 | Correct | 5 ms | 4972 KB | Output is correct |
16 | Correct | 4 ms | 4972 KB | Output is correct |
17 | Correct | 4 ms | 4972 KB | Output is correct |
18 | Correct | 4 ms | 4992 KB | Output is correct |
19 | Correct | 4 ms | 4972 KB | Output is correct |
20 | Correct | 4 ms | 4972 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 4 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 5 ms | 4992 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Correct | 4 ms | 4972 KB | Output is correct |
7 | Correct | 3 ms | 4972 KB | Output is correct |
8 | Correct | 4 ms | 4972 KB | Output is correct |
9 | Correct | 3 ms | 4972 KB | Output is correct |
10 | Correct | 4 ms | 4972 KB | Output is correct |
11 | Correct | 4 ms | 4972 KB | Output is correct |
12 | Correct | 3 ms | 4972 KB | Output is correct |
13 | Correct | 4 ms | 4972 KB | Output is correct |
14 | Correct | 4 ms | 4972 KB | Output is correct |
15 | Correct | 5 ms | 4972 KB | Output is correct |
16 | Correct | 4 ms | 4972 KB | Output is correct |
17 | Correct | 4 ms | 4972 KB | Output is correct |
18 | Correct | 4 ms | 4992 KB | Output is correct |
19 | Correct | 4 ms | 4972 KB | Output is correct |
20 | Correct | 4 ms | 4972 KB | Output is correct |
21 | Correct | 4 ms | 5228 KB | Output is correct |
22 | Correct | 5 ms | 4972 KB | Output is correct |
23 | Correct | 5 ms | 4972 KB | Output is correct |
24 | Correct | 4 ms | 4972 KB | Output is correct |
25 | Correct | 4 ms | 5100 KB | Output is correct |
26 | Correct | 4 ms | 5100 KB | Output is correct |
27 | Correct | 4 ms | 5100 KB | Output is correct |
28 | Correct | 4 ms | 5100 KB | Output is correct |
29 | Correct | 4 ms | 5100 KB | Output is correct |
30 | Correct | 4 ms | 5100 KB | Output is correct |
31 | Correct | 4 ms | 5100 KB | Output is correct |
32 | Correct | 4 ms | 5100 KB | Output is correct |
33 | Correct | 4 ms | 5100 KB | Output is correct |
34 | Correct | 4 ms | 5100 KB | Output is correct |
35 | Correct | 4 ms | 5100 KB | Output is correct |
36 | Correct | 4 ms | 5100 KB | Output is correct |
37 | Correct | 4 ms | 5100 KB | Output is correct |
38 | Correct | 4 ms | 5100 KB | Output is correct |
39 | Correct | 5 ms | 5100 KB | Output is correct |
40 | Correct | 5 ms | 5100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 4972 KB | Output is correct |
2 | Correct | 4 ms | 4972 KB | Output is correct |
3 | Correct | 4 ms | 4972 KB | Output is correct |
4 | Correct | 5 ms | 4992 KB | Output is correct |
5 | Correct | 4 ms | 4972 KB | Output is correct |
6 | Correct | 4 ms | 4972 KB | Output is correct |
7 | Correct | 3 ms | 4972 KB | Output is correct |
8 | Correct | 4 ms | 4972 KB | Output is correct |
9 | Correct | 3 ms | 4972 KB | Output is correct |
10 | Correct | 4 ms | 4972 KB | Output is correct |
11 | Correct | 4 ms | 4972 KB | Output is correct |
12 | Correct | 3 ms | 4972 KB | Output is correct |
13 | Correct | 4 ms | 4972 KB | Output is correct |
14 | Correct | 4 ms | 4972 KB | Output is correct |
15 | Correct | 5 ms | 4972 KB | Output is correct |
16 | Correct | 4 ms | 4972 KB | Output is correct |
17 | Correct | 4 ms | 4972 KB | Output is correct |
18 | Correct | 4 ms | 4992 KB | Output is correct |
19 | Correct | 4 ms | 4972 KB | Output is correct |
20 | Correct | 4 ms | 4972 KB | Output is correct |
21 | Correct | 4 ms | 5228 KB | Output is correct |
22 | Correct | 5 ms | 4972 KB | Output is correct |
23 | Correct | 5 ms | 4972 KB | Output is correct |
24 | Correct | 4 ms | 4972 KB | Output is correct |
25 | Correct | 4 ms | 5100 KB | Output is correct |
26 | Correct | 4 ms | 5100 KB | Output is correct |
27 | Correct | 4 ms | 5100 KB | Output is correct |
28 | Correct | 4 ms | 5100 KB | Output is correct |
29 | Correct | 4 ms | 5100 KB | Output is correct |
30 | Correct | 4 ms | 5100 KB | Output is correct |
31 | Correct | 4 ms | 5100 KB | Output is correct |
32 | Correct | 4 ms | 5100 KB | Output is correct |
33 | Correct | 4 ms | 5100 KB | Output is correct |
34 | Correct | 4 ms | 5100 KB | Output is correct |
35 | Correct | 4 ms | 5100 KB | Output is correct |
36 | Correct | 4 ms | 5100 KB | Output is correct |
37 | Correct | 4 ms | 5100 KB | Output is correct |
38 | Correct | 4 ms | 5100 KB | Output is correct |
39 | Correct | 5 ms | 5100 KB | Output is correct |
40 | Correct | 5 ms | 5100 KB | Output is correct |
41 | Correct | 51 ms | 10344 KB | Output is correct |
42 | Correct | 36 ms | 7404 KB | Output is correct |
43 | Correct | 35 ms | 7404 KB | Output is correct |
44 | Correct | 34 ms | 7532 KB | Output is correct |
45 | Correct | 34 ms | 7532 KB | Output is correct |
46 | Correct | 89 ms | 9964 KB | Output is correct |
47 | Correct | 86 ms | 9964 KB | Output is correct |
48 | Correct | 110 ms | 10092 KB | Output is correct |
49 | Correct | 110 ms | 10112 KB | Output is correct |
50 | Correct | 21 ms | 6508 KB | Output is correct |
51 | Correct | 20 ms | 6540 KB | Output is correct |
52 | Correct | 20 ms | 6508 KB | Output is correct |
53 | Correct | 39 ms | 7788 KB | Output is correct |
54 | Correct | 39 ms | 7916 KB | Output is correct |
55 | Correct | 40 ms | 7916 KB | Output is correct |
56 | Correct | 5 ms | 5248 KB | Output is correct |
57 | Correct | 12 ms | 6892 KB | Output is correct |
58 | Correct | 31 ms | 12908 KB | Output is correct |
59 | Correct | 74 ms | 14572 KB | Output is correct |
60 | Correct | 54 ms | 10856 KB | Output is correct |
61 | Correct | 65 ms | 10604 KB | Output is correct |