#include <bits/stdc++.h>
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
const int N = 2e5 + 10;
int n, t, d, dep[N], sz[N], st[N], en[N], hv[N];
vector<int> g[N];
multiset<int> s;
void dfs( int u, int p ) {
st[u] = ++t, sz[u] = 1, dep[u] = dep[p] + 1;
pii ret( -1e9, -1 );
for( int v : g[u] ) if( v != p ) {
dfs( v, u );
sz[u] += sz[v];
ret = max( ret, pii( sz[v], v ) );
}
hv[u] = ret.y, en[u] = t;
}
void sack( multiset<int> &s, int u, int p ) {
if( hv[u] != -1 ) sack( s, hv[u], u );
multiset<int> t;
for( int v : g[u] ) if( v != p && v != hv[u] ) {
sack( t, v, u );
while( !s.empty() && !t.empty() && *s.begin() + *t.begin() - 2*dep[u] < d ) {
if( *s.begin() < *t.begin() ) s.erase( s.begin() );
else t.erase( t.begin() );
}
for( int x : t ) s.emplace( x );
t.clear();
}
t.emplace( dep[u] );
while( !s.empty() && !t.empty() && *s.begin() + *t.begin() - 2*dep[u] < d ) {
if( *s.begin() < *t.begin() ) s.erase( s.begin() );
else t.erase( t.begin() );
}
for( int x : t ) s.emplace( x );
t.clear();
}
int main()
{
scanf("%d %d",&n,&d);
for( int i = 1, a ; i < n ; i++ ) {
scanf("%d",&a);
g[a].emplace_back( i ), g[i].emplace_back( a );
}
dfs( 0, 0 );
sack( s, 0, 0 );
printf("%d",s.size());
return 0;
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:55:25: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::multiset<int>::size_type {aka long unsigned int}' [-Wformat=]
printf("%d",s.size());
~~~~~~~~^
catinatree.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&n,&d);
~~~~~^~~~~~~~~~~~~~~
catinatree.cpp:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&a);
~~~~~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 KB |
Output is correct |
2 |
Correct |
8 ms |
4984 KB |
Output is correct |
3 |
Correct |
7 ms |
4984 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
4984 KB |
Output is correct |
6 |
Correct |
7 ms |
5068 KB |
Output is correct |
7 |
Correct |
7 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
4984 KB |
Output is correct |
9 |
Correct |
8 ms |
4984 KB |
Output is correct |
10 |
Correct |
7 ms |
4984 KB |
Output is correct |
11 |
Correct |
7 ms |
4984 KB |
Output is correct |
12 |
Correct |
7 ms |
4984 KB |
Output is correct |
13 |
Correct |
7 ms |
4984 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
8 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
4984 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
7 ms |
4984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 KB |
Output is correct |
2 |
Correct |
8 ms |
4984 KB |
Output is correct |
3 |
Correct |
7 ms |
4984 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
4984 KB |
Output is correct |
6 |
Correct |
7 ms |
5068 KB |
Output is correct |
7 |
Correct |
7 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
4984 KB |
Output is correct |
9 |
Correct |
8 ms |
4984 KB |
Output is correct |
10 |
Correct |
7 ms |
4984 KB |
Output is correct |
11 |
Correct |
7 ms |
4984 KB |
Output is correct |
12 |
Correct |
7 ms |
4984 KB |
Output is correct |
13 |
Correct |
7 ms |
4984 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
8 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
4984 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
7 ms |
4984 KB |
Output is correct |
21 |
Correct |
8 ms |
5368 KB |
Output is correct |
22 |
Correct |
8 ms |
5112 KB |
Output is correct |
23 |
Correct |
8 ms |
5112 KB |
Output is correct |
24 |
Correct |
8 ms |
5112 KB |
Output is correct |
25 |
Correct |
9 ms |
5112 KB |
Output is correct |
26 |
Correct |
8 ms |
5112 KB |
Output is correct |
27 |
Correct |
8 ms |
5112 KB |
Output is correct |
28 |
Correct |
8 ms |
5112 KB |
Output is correct |
29 |
Correct |
8 ms |
5112 KB |
Output is correct |
30 |
Correct |
8 ms |
5112 KB |
Output is correct |
31 |
Correct |
8 ms |
5116 KB |
Output is correct |
32 |
Correct |
8 ms |
5112 KB |
Output is correct |
33 |
Correct |
8 ms |
5112 KB |
Output is correct |
34 |
Correct |
8 ms |
5112 KB |
Output is correct |
35 |
Correct |
8 ms |
5112 KB |
Output is correct |
36 |
Correct |
8 ms |
5112 KB |
Output is correct |
37 |
Correct |
8 ms |
5112 KB |
Output is correct |
38 |
Correct |
8 ms |
5112 KB |
Output is correct |
39 |
Correct |
8 ms |
5240 KB |
Output is correct |
40 |
Correct |
8 ms |
5368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5112 KB |
Output is correct |
2 |
Correct |
8 ms |
4984 KB |
Output is correct |
3 |
Correct |
7 ms |
4984 KB |
Output is correct |
4 |
Correct |
8 ms |
5112 KB |
Output is correct |
5 |
Correct |
9 ms |
4984 KB |
Output is correct |
6 |
Correct |
7 ms |
5068 KB |
Output is correct |
7 |
Correct |
7 ms |
4984 KB |
Output is correct |
8 |
Correct |
7 ms |
4984 KB |
Output is correct |
9 |
Correct |
8 ms |
4984 KB |
Output is correct |
10 |
Correct |
7 ms |
4984 KB |
Output is correct |
11 |
Correct |
7 ms |
4984 KB |
Output is correct |
12 |
Correct |
7 ms |
4984 KB |
Output is correct |
13 |
Correct |
7 ms |
4984 KB |
Output is correct |
14 |
Correct |
7 ms |
5112 KB |
Output is correct |
15 |
Correct |
8 ms |
4984 KB |
Output is correct |
16 |
Correct |
8 ms |
5112 KB |
Output is correct |
17 |
Correct |
8 ms |
5112 KB |
Output is correct |
18 |
Correct |
8 ms |
4984 KB |
Output is correct |
19 |
Correct |
7 ms |
4984 KB |
Output is correct |
20 |
Correct |
7 ms |
4984 KB |
Output is correct |
21 |
Correct |
8 ms |
5368 KB |
Output is correct |
22 |
Correct |
8 ms |
5112 KB |
Output is correct |
23 |
Correct |
8 ms |
5112 KB |
Output is correct |
24 |
Correct |
8 ms |
5112 KB |
Output is correct |
25 |
Correct |
9 ms |
5112 KB |
Output is correct |
26 |
Correct |
8 ms |
5112 KB |
Output is correct |
27 |
Correct |
8 ms |
5112 KB |
Output is correct |
28 |
Correct |
8 ms |
5112 KB |
Output is correct |
29 |
Correct |
8 ms |
5112 KB |
Output is correct |
30 |
Correct |
8 ms |
5112 KB |
Output is correct |
31 |
Correct |
8 ms |
5116 KB |
Output is correct |
32 |
Correct |
8 ms |
5112 KB |
Output is correct |
33 |
Correct |
8 ms |
5112 KB |
Output is correct |
34 |
Correct |
8 ms |
5112 KB |
Output is correct |
35 |
Correct |
8 ms |
5112 KB |
Output is correct |
36 |
Correct |
8 ms |
5112 KB |
Output is correct |
37 |
Correct |
8 ms |
5112 KB |
Output is correct |
38 |
Correct |
8 ms |
5112 KB |
Output is correct |
39 |
Correct |
8 ms |
5240 KB |
Output is correct |
40 |
Correct |
8 ms |
5368 KB |
Output is correct |
41 |
Correct |
104 ms |
18164 KB |
Output is correct |
42 |
Correct |
148 ms |
15992 KB |
Output is correct |
43 |
Correct |
71 ms |
10744 KB |
Output is correct |
44 |
Correct |
69 ms |
10744 KB |
Output is correct |
45 |
Correct |
73 ms |
10748 KB |
Output is correct |
46 |
Correct |
269 ms |
23160 KB |
Output is correct |
47 |
Correct |
183 ms |
16504 KB |
Output is correct |
48 |
Correct |
178 ms |
16504 KB |
Output is correct |
49 |
Correct |
191 ms |
16764 KB |
Output is correct |
50 |
Correct |
60 ms |
11128 KB |
Output is correct |
51 |
Correct |
56 ms |
11000 KB |
Output is correct |
52 |
Correct |
58 ms |
11000 KB |
Output is correct |
53 |
Correct |
142 ms |
17276 KB |
Output is correct |
54 |
Correct |
129 ms |
17016 KB |
Output is correct |
55 |
Correct |
133 ms |
17016 KB |
Output is correct |
56 |
Correct |
8 ms |
5368 KB |
Output is correct |
57 |
Correct |
16 ms |
9336 KB |
Output is correct |
58 |
Correct |
54 ms |
24824 KB |
Output is correct |
59 |
Correct |
135 ms |
32120 KB |
Output is correct |
60 |
Correct |
100 ms |
18036 KB |
Output is correct |
61 |
Correct |
109 ms |
15864 KB |
Output is correct |