#include<bits/stdc++.h>
#define ll long long
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
//#define int int64_t
using namespace std;
typedef pair<int, int> pii;
const int N = (int)2e5 + 10;
int dep[N], n, d, p[N], ans = 0;
int in[N], out[N], T, u, cur, par, rem;
vector<int> adj[N];
vector<pii> v;
struct TSegment {
int tree[N << 2], lim;
void init() {
memset(tree, 0x3f, sizeof(tree));
for(lim = 1; lim <= n; lim <<= 1);
}
int get(int x){
x += lim;
int ret = 1e9;
while(x){
ret = min(ret, tree[x]);
x >>= 1;
}
return ret;
}
void upd(int s, int e, int x){
s += lim;
e += lim;
while(s < e){
if(s%2 == 1) tree[s] = min(tree[s], x);
if(e%2 == 0) tree[e] = min(tree[e], x);
s = (s+1)/2;
e = (e-1)/2;
}
if(s == e) tree[s] = min(tree[s], x);
}
} it;
void DFS(int u) {
in[u] = ++T;
for(int v: adj[u]) DFS(v);
out[u] = T;
}
int32_t main() {
// ios_base::sync_with_stdio(0);
// cin.tie(0); cout.tie(0);
// #define FileName "test"
// if(fopen(FileName".inp", "r")) {
// freopen(FileName".inp", "r", stdin);
// freopen(FileName".out", "w", stdout);
// }
scanf("%d %d", &n, &d); v.pb(0, 0);
for(int i = 1; i < n; ++i) {
scanf("%d", &p[i]);
adj[p[i]].pb(i);
dep[i] = dep[p[i]] + 1;
v.pb(dep[i], i);
}
sort(v.begin(), v.end(), greater<pii>());
DFS(0); it.init();
for(pii& node: v) {
u = node.se;
if(it.get(in[u]) + dep[u] >= d) {
++ans; cur = u;
while(1) {
it.upd(in[cur], out[cur], dep[u] - 2 * dep[cur]);
if(cur == 0) break;
cur = p[cur];
}
}
}
cout << ans;
}
Compilation message
catinatree.cpp: In function 'int32_t main()':
catinatree.cpp:61:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &d); v.pb(0, 0);
~~~~~^~~~~~~~~~~~~~~~~
catinatree.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &p[i]);
~~~~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8188 KB |
Output is correct |
2 |
Correct |
10 ms |
8184 KB |
Output is correct |
3 |
Correct |
10 ms |
8188 KB |
Output is correct |
4 |
Correct |
10 ms |
8184 KB |
Output is correct |
5 |
Correct |
11 ms |
8184 KB |
Output is correct |
6 |
Correct |
10 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8184 KB |
Output is correct |
9 |
Correct |
10 ms |
8184 KB |
Output is correct |
10 |
Correct |
9 ms |
8184 KB |
Output is correct |
11 |
Correct |
10 ms |
8184 KB |
Output is correct |
12 |
Correct |
10 ms |
8184 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
10 ms |
8184 KB |
Output is correct |
15 |
Correct |
10 ms |
8184 KB |
Output is correct |
16 |
Correct |
9 ms |
8216 KB |
Output is correct |
17 |
Correct |
11 ms |
8184 KB |
Output is correct |
18 |
Correct |
9 ms |
8188 KB |
Output is correct |
19 |
Correct |
9 ms |
8184 KB |
Output is correct |
20 |
Correct |
9 ms |
8184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8188 KB |
Output is correct |
2 |
Correct |
10 ms |
8184 KB |
Output is correct |
3 |
Correct |
10 ms |
8188 KB |
Output is correct |
4 |
Correct |
10 ms |
8184 KB |
Output is correct |
5 |
Correct |
11 ms |
8184 KB |
Output is correct |
6 |
Correct |
10 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8184 KB |
Output is correct |
9 |
Correct |
10 ms |
8184 KB |
Output is correct |
10 |
Correct |
9 ms |
8184 KB |
Output is correct |
11 |
Correct |
10 ms |
8184 KB |
Output is correct |
12 |
Correct |
10 ms |
8184 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
10 ms |
8184 KB |
Output is correct |
15 |
Correct |
10 ms |
8184 KB |
Output is correct |
16 |
Correct |
9 ms |
8216 KB |
Output is correct |
17 |
Correct |
11 ms |
8184 KB |
Output is correct |
18 |
Correct |
9 ms |
8188 KB |
Output is correct |
19 |
Correct |
9 ms |
8184 KB |
Output is correct |
20 |
Correct |
9 ms |
8184 KB |
Output is correct |
21 |
Correct |
11 ms |
8312 KB |
Output is correct |
22 |
Correct |
10 ms |
8184 KB |
Output is correct |
23 |
Correct |
10 ms |
8184 KB |
Output is correct |
24 |
Correct |
10 ms |
8184 KB |
Output is correct |
25 |
Correct |
10 ms |
8184 KB |
Output is correct |
26 |
Correct |
10 ms |
8184 KB |
Output is correct |
27 |
Correct |
10 ms |
8184 KB |
Output is correct |
28 |
Correct |
10 ms |
8312 KB |
Output is correct |
29 |
Correct |
11 ms |
8312 KB |
Output is correct |
30 |
Correct |
10 ms |
8312 KB |
Output is correct |
31 |
Correct |
10 ms |
8312 KB |
Output is correct |
32 |
Correct |
10 ms |
8188 KB |
Output is correct |
33 |
Correct |
10 ms |
8184 KB |
Output is correct |
34 |
Correct |
10 ms |
8184 KB |
Output is correct |
35 |
Correct |
10 ms |
8184 KB |
Output is correct |
36 |
Correct |
13 ms |
8188 KB |
Output is correct |
37 |
Correct |
10 ms |
8184 KB |
Output is correct |
38 |
Correct |
10 ms |
8184 KB |
Output is correct |
39 |
Correct |
10 ms |
8184 KB |
Output is correct |
40 |
Correct |
21 ms |
8312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
8188 KB |
Output is correct |
2 |
Correct |
10 ms |
8184 KB |
Output is correct |
3 |
Correct |
10 ms |
8188 KB |
Output is correct |
4 |
Correct |
10 ms |
8184 KB |
Output is correct |
5 |
Correct |
11 ms |
8184 KB |
Output is correct |
6 |
Correct |
10 ms |
8184 KB |
Output is correct |
7 |
Correct |
9 ms |
8184 KB |
Output is correct |
8 |
Correct |
9 ms |
8184 KB |
Output is correct |
9 |
Correct |
10 ms |
8184 KB |
Output is correct |
10 |
Correct |
9 ms |
8184 KB |
Output is correct |
11 |
Correct |
10 ms |
8184 KB |
Output is correct |
12 |
Correct |
10 ms |
8184 KB |
Output is correct |
13 |
Correct |
9 ms |
8184 KB |
Output is correct |
14 |
Correct |
10 ms |
8184 KB |
Output is correct |
15 |
Correct |
10 ms |
8184 KB |
Output is correct |
16 |
Correct |
9 ms |
8216 KB |
Output is correct |
17 |
Correct |
11 ms |
8184 KB |
Output is correct |
18 |
Correct |
9 ms |
8188 KB |
Output is correct |
19 |
Correct |
9 ms |
8184 KB |
Output is correct |
20 |
Correct |
9 ms |
8184 KB |
Output is correct |
21 |
Correct |
11 ms |
8312 KB |
Output is correct |
22 |
Correct |
10 ms |
8184 KB |
Output is correct |
23 |
Correct |
10 ms |
8184 KB |
Output is correct |
24 |
Correct |
10 ms |
8184 KB |
Output is correct |
25 |
Correct |
10 ms |
8184 KB |
Output is correct |
26 |
Correct |
10 ms |
8184 KB |
Output is correct |
27 |
Correct |
10 ms |
8184 KB |
Output is correct |
28 |
Correct |
10 ms |
8312 KB |
Output is correct |
29 |
Correct |
11 ms |
8312 KB |
Output is correct |
30 |
Correct |
10 ms |
8312 KB |
Output is correct |
31 |
Correct |
10 ms |
8312 KB |
Output is correct |
32 |
Correct |
10 ms |
8188 KB |
Output is correct |
33 |
Correct |
10 ms |
8184 KB |
Output is correct |
34 |
Correct |
10 ms |
8184 KB |
Output is correct |
35 |
Correct |
10 ms |
8184 KB |
Output is correct |
36 |
Correct |
13 ms |
8188 KB |
Output is correct |
37 |
Correct |
10 ms |
8184 KB |
Output is correct |
38 |
Correct |
10 ms |
8184 KB |
Output is correct |
39 |
Correct |
10 ms |
8184 KB |
Output is correct |
40 |
Correct |
21 ms |
8312 KB |
Output is correct |
41 |
Correct |
92 ms |
16484 KB |
Output is correct |
42 |
Correct |
139 ms |
12280 KB |
Output is correct |
43 |
Correct |
59 ms |
12264 KB |
Output is correct |
44 |
Correct |
58 ms |
12268 KB |
Output is correct |
45 |
Correct |
58 ms |
12268 KB |
Output is correct |
46 |
Correct |
259 ms |
16224 KB |
Output is correct |
47 |
Correct |
130 ms |
17256 KB |
Output is correct |
48 |
Correct |
136 ms |
17356 KB |
Output is correct |
49 |
Correct |
135 ms |
17252 KB |
Output is correct |
50 |
Correct |
42 ms |
11500 KB |
Output is correct |
51 |
Correct |
41 ms |
11628 KB |
Output is correct |
52 |
Correct |
41 ms |
11500 KB |
Output is correct |
53 |
Correct |
74 ms |
14692 KB |
Output is correct |
54 |
Correct |
78 ms |
14700 KB |
Output is correct |
55 |
Correct |
75 ms |
14916 KB |
Output is correct |
56 |
Correct |
23 ms |
8312 KB |
Output is correct |
57 |
Correct |
27 ms |
9972 KB |
Output is correct |
58 |
Correct |
93 ms |
16748 KB |
Output is correct |
59 |
Correct |
173 ms |
20452 KB |
Output is correct |
60 |
Correct |
95 ms |
18020 KB |
Output is correct |
61 |
Correct |
115 ms |
17764 KB |
Output is correct |