# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
943716 | 2024-03-11T18:36:01 Z | stefanneagu | Cat in a tree (BOI17_catinatree) | C++17 | 122 ms | 26712 KB |
#include <bits/stdc++.h> using namespace std; const int nmax = 2e5 + 1; int k, sz[nmax], l[nmax]; vector<vector<int>> adj; void dfs(int i, int tata) { for(auto it : adj[i]) { if(it != tata) { dfs(it, i); } } int x = 1; vector<int> v; v.push_back(0); // daca pot sa bag la nodul i? for(auto it : adj[i]) { if(it != tata) { x += sz[it]; v.push_back(l[it]); } } sort(v.begin(), v.end()); int ind = 0; while(ind < v.size() - 1 && v[ind] + v[ind + 1] < k) { ind ++; x --; } l[i] = v[ind] + 1; sz[i] = x; } int main() { int n; cin >> n >> k; adj.resize(n + 1); for(int i = 2; i <= n; i ++) { int a; cin >> a; a ++; adj[a].push_back(i); adj[i].push_back(a); } dfs(1, 0); cout << sz[1]; return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 440 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 344 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 440 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 344 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 2 ms | 604 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 1 ms | 344 KB | Output is correct |
26 | Correct | 1 ms | 344 KB | Output is correct |
27 | Correct | 1 ms | 344 KB | Output is correct |
28 | Correct | 1 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 348 KB | Output is correct |
30 | Correct | 1 ms | 344 KB | Output is correct |
31 | Correct | 1 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 348 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 600 KB | Output is correct |
35 | Correct | 1 ms | 348 KB | Output is correct |
36 | Correct | 1 ms | 348 KB | Output is correct |
37 | Correct | 1 ms | 344 KB | Output is correct |
38 | Correct | 1 ms | 348 KB | Output is correct |
39 | Correct | 1 ms | 604 KB | Output is correct |
40 | Correct | 1 ms | 604 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 344 KB | Output is correct |
2 | Correct | 1 ms | 348 KB | Output is correct |
3 | Correct | 0 ms | 348 KB | Output is correct |
4 | Correct | 1 ms | 344 KB | Output is correct |
5 | Correct | 0 ms | 348 KB | Output is correct |
6 | Correct | 1 ms | 344 KB | Output is correct |
7 | Correct | 0 ms | 440 KB | Output is correct |
8 | Correct | 1 ms | 344 KB | Output is correct |
9 | Correct | 1 ms | 348 KB | Output is correct |
10 | Correct | 1 ms | 348 KB | Output is correct |
11 | Correct | 1 ms | 348 KB | Output is correct |
12 | Correct | 1 ms | 348 KB | Output is correct |
13 | Correct | 1 ms | 344 KB | Output is correct |
14 | Correct | 1 ms | 600 KB | Output is correct |
15 | Correct | 1 ms | 348 KB | Output is correct |
16 | Correct | 1 ms | 344 KB | Output is correct |
17 | Correct | 0 ms | 348 KB | Output is correct |
18 | Correct | 1 ms | 348 KB | Output is correct |
19 | Correct | 0 ms | 348 KB | Output is correct |
20 | Correct | 1 ms | 348 KB | Output is correct |
21 | Correct | 2 ms | 604 KB | Output is correct |
22 | Correct | 1 ms | 348 KB | Output is correct |
23 | Correct | 0 ms | 348 KB | Output is correct |
24 | Correct | 1 ms | 348 KB | Output is correct |
25 | Correct | 1 ms | 344 KB | Output is correct |
26 | Correct | 1 ms | 344 KB | Output is correct |
27 | Correct | 1 ms | 344 KB | Output is correct |
28 | Correct | 1 ms | 348 KB | Output is correct |
29 | Correct | 1 ms | 348 KB | Output is correct |
30 | Correct | 1 ms | 344 KB | Output is correct |
31 | Correct | 1 ms | 348 KB | Output is correct |
32 | Correct | 1 ms | 348 KB | Output is correct |
33 | Correct | 1 ms | 348 KB | Output is correct |
34 | Correct | 1 ms | 600 KB | Output is correct |
35 | Correct | 1 ms | 348 KB | Output is correct |
36 | Correct | 1 ms | 348 KB | Output is correct |
37 | Correct | 1 ms | 344 KB | Output is correct |
38 | Correct | 1 ms | 348 KB | Output is correct |
39 | Correct | 1 ms | 604 KB | Output is correct |
40 | Correct | 1 ms | 604 KB | Output is correct |
41 | Correct | 67 ms | 13520 KB | Output is correct |
42 | Correct | 36 ms | 7248 KB | Output is correct |
43 | Correct | 37 ms | 7188 KB | Output is correct |
44 | Correct | 41 ms | 7176 KB | Output is correct |
45 | Correct | 45 ms | 7196 KB | Output is correct |
46 | Correct | 85 ms | 14132 KB | Output is correct |
47 | Correct | 87 ms | 14128 KB | Output is correct |
48 | Correct | 122 ms | 14320 KB | Output is correct |
49 | Correct | 103 ms | 14160 KB | Output is correct |
50 | Correct | 27 ms | 7568 KB | Output is correct |
51 | Correct | 29 ms | 7544 KB | Output is correct |
52 | Correct | 43 ms | 7368 KB | Output is correct |
53 | Correct | 74 ms | 14764 KB | Output is correct |
54 | Correct | 74 ms | 14640 KB | Output is correct |
55 | Correct | 112 ms | 14772 KB | Output is correct |
56 | Correct | 2 ms | 604 KB | Output is correct |
57 | Correct | 10 ms | 4188 KB | Output is correct |
58 | Correct | 42 ms | 18460 KB | Output is correct |
59 | Correct | 102 ms | 26712 KB | Output is correct |
60 | Correct | 75 ms | 14184 KB | Output is correct |
61 | Correct | 84 ms | 13492 KB | Output is correct |