#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 19
#define MAXN 200005
vector<vector<int>> graph;
int up[LOGN][MAXN], depth[MAXN];
void dfs(int node, int parent) {
for (auto u : graph[node]) {
if (u == parent)
continue;
depth[u] = depth[node] + 1;
up[0][u] = node;
for (int i = 1; i < LOGN; i++)
up[i][u] = up[i-1][up[i-1][u]];
dfs(u, node);
}
}
int find(int node, int k) {
for (int i = 0; i < LOGN; i++) {
if ((1<<i) & k)
node = up[i][node];
}
return node;
}
int lca(int a, int b) {
if (depth[b] > depth[a])
swap(a, b);
a = find(a, depth[a] - depth[b]);
if (a == b)
return a;
for (int i = LOGN-1; i >= 0; i--) {
if (up[i][a] != up[i][b]) {
a = up[i][a];
b = up[i][b];
}
}
return up[0][a];
}
int dist(int a, int b) {
return depth[a] + depth[b] - 2*depth[lca(a, b)];
}
bool marked[MAXN];
vector<int> par, sz;
int get_sz(int node, int parent) {
for (auto u : graph[node]) {
if (u == parent || marked[u])
continue;
sz[node] += get_sz(u, node);
}
return sz[node];
}
int find_centro(int node, int parent, int n) {
for (auto u : graph[node]) {
if (u != parent && !marked[u] && sz[u] * 2 > n)
return find_centro(u, node, n);
}
return node;
}
void decompose(int node, int parent) {
int n = get_sz(node, parent);
int centro = find_centro(node, node, n);
par[centro] = parent;
marked[centro] = true;
for (auto u : graph[centro]) {
if (!marked[u] && u != parent)
decompose(u, centro);
}
}
vector<int> nearest;
int main() {
int N, D, x;
scanf("%d %d", &N, &D);
graph = vector<vector<int>>(N, vector<int>());
nearest = vector<int>(N, 1e9);
par = vector<int>(N, -1);
sz = vector<int>(N, 1);
for (int i = 1; i < N; i++) {
scanf("%d", &x);
graph[x].push_back(i);
graph[i].push_back(x);
}
for (int i = 0; i < LOGN; i++)
up[i][0] = 0;
dfs(0, 0);
decompose(0, -1);
vector<pair<int,int>> order;
for (int i = 0; i < N; i++)
order.push_back({depth[i], i});
sort(order.rbegin(), order.rend());
int ans = 0;
for (auto u : order) {
int node = u.s;
int now = node;
int mn_dist = 1e9;
while (now != -1) {
mn_dist = min(mn_dist, dist(node, now) + nearest[now]);
now = par[now];
}
if (mn_dist >= D) {
ans++;
int now = node;
while (now != -1) {
nearest[now] = min(nearest[now], dist(node, now));
now = par[now];
}
}
}
printf("%d\n", ans);
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:87:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | scanf("%d %d", &N, &D);
| ~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:94:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
94 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
304 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
304 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
432 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
568 KB |
Output is correct |
31 |
Correct |
2 ms |
596 KB |
Output is correct |
32 |
Correct |
1 ms |
596 KB |
Output is correct |
33 |
Correct |
1 ms |
564 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
1 ms |
596 KB |
Output is correct |
36 |
Correct |
1 ms |
596 KB |
Output is correct |
37 |
Correct |
2 ms |
568 KB |
Output is correct |
38 |
Correct |
2 ms |
596 KB |
Output is correct |
39 |
Correct |
2 ms |
596 KB |
Output is correct |
40 |
Correct |
4 ms |
696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
0 ms |
340 KB |
Output is correct |
3 |
Correct |
0 ms |
308 KB |
Output is correct |
4 |
Correct |
0 ms |
340 KB |
Output is correct |
5 |
Correct |
0 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
0 ms |
340 KB |
Output is correct |
9 |
Correct |
0 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
0 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
304 KB |
Output is correct |
14 |
Correct |
0 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
304 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
0 ms |
340 KB |
Output is correct |
20 |
Correct |
0 ms |
340 KB |
Output is correct |
21 |
Correct |
3 ms |
724 KB |
Output is correct |
22 |
Correct |
1 ms |
432 KB |
Output is correct |
23 |
Correct |
1 ms |
468 KB |
Output is correct |
24 |
Correct |
1 ms |
468 KB |
Output is correct |
25 |
Correct |
1 ms |
468 KB |
Output is correct |
26 |
Correct |
1 ms |
468 KB |
Output is correct |
27 |
Correct |
1 ms |
468 KB |
Output is correct |
28 |
Correct |
1 ms |
596 KB |
Output is correct |
29 |
Correct |
1 ms |
596 KB |
Output is correct |
30 |
Correct |
1 ms |
568 KB |
Output is correct |
31 |
Correct |
2 ms |
596 KB |
Output is correct |
32 |
Correct |
1 ms |
596 KB |
Output is correct |
33 |
Correct |
1 ms |
564 KB |
Output is correct |
34 |
Correct |
1 ms |
596 KB |
Output is correct |
35 |
Correct |
1 ms |
596 KB |
Output is correct |
36 |
Correct |
1 ms |
596 KB |
Output is correct |
37 |
Correct |
2 ms |
568 KB |
Output is correct |
38 |
Correct |
2 ms |
596 KB |
Output is correct |
39 |
Correct |
2 ms |
596 KB |
Output is correct |
40 |
Correct |
4 ms |
696 KB |
Output is correct |
41 |
Correct |
110 ms |
30848 KB |
Output is correct |
42 |
Correct |
163 ms |
16392 KB |
Output is correct |
43 |
Correct |
105 ms |
16388 KB |
Output is correct |
44 |
Correct |
129 ms |
16476 KB |
Output is correct |
45 |
Correct |
94 ms |
16484 KB |
Output is correct |
46 |
Correct |
275 ms |
32060 KB |
Output is correct |
47 |
Correct |
274 ms |
32060 KB |
Output is correct |
48 |
Correct |
291 ms |
32076 KB |
Output is correct |
49 |
Correct |
252 ms |
32032 KB |
Output is correct |
50 |
Correct |
91 ms |
16820 KB |
Output is correct |
51 |
Correct |
77 ms |
16920 KB |
Output is correct |
52 |
Correct |
74 ms |
16816 KB |
Output is correct |
53 |
Correct |
179 ms |
32868 KB |
Output is correct |
54 |
Correct |
180 ms |
32872 KB |
Output is correct |
55 |
Correct |
200 ms |
32868 KB |
Output is correct |
56 |
Correct |
6 ms |
828 KB |
Output is correct |
57 |
Correct |
588 ms |
5556 KB |
Output is correct |
58 |
Execution timed out |
1047 ms |
22240 KB |
Time limit exceeded |
59 |
Halted |
0 ms |
0 KB |
- |