#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;
vector<int> adj[maxn];
int nivel[maxn], nivelCentroid[maxn], sub[maxn], distMin[maxn], dist[20][maxn], paiCentroid[maxn];
bool removed[maxn];
int n, d;
vector<int> vert;
void dfsInit( int cur, int pai ){
sub[cur] = 1;
for( int viz : adj[cur] ){
if( viz == pai || removed[viz] ) continue;
dfsInit( viz, cur );
sub[cur] += sub[viz];
}
}
int findCen( int cur, int pai, int sz ){
for( int viz : adj[cur] ){
if( viz == pai || removed[viz] ) continue;
if( sub[viz] > sz/2 ) return findCen( viz, cur, sz );
}
return cur;
}
void dfs( int cur, int pai, int nivel ){
for( int viz : adj[cur] ){
if( viz == pai || removed[viz] ) continue;
dist[nivel][viz] = dist[nivel][cur] + 1;
dfs( viz, cur, nivel );
}
}
void decompose( int node, int pai, int nivel ){
dfsInit( node, node );
int cen = findCen( node, node, sub[node] );
paiCentroid[cen] = pai;
nivelCentroid[cen] = nivel;
dfs( cen, cen, nivel );
removed[cen] = true;
for( int viz : adj[cen] ) if( !removed[viz] ) decompose( viz, cen, nivel + 1 );
}
void update( int x ){
int cur = x;
while( cur != -1 ){
distMin[cur] = min( distMin[cur], dist[nivelCentroid[cur]][x] );
cur = paiCentroid[cur];
}
}
int query( int x ){
int resp = maxn;
int cur = x;
while( cur != -1 ){
resp = min( resp, dist[nivelCentroid[cur]][x] + distMin[cur] );
cur = paiCentroid[cur];
}
return resp;
}
void dfs2( int cur, int pai ){
for( int viz : adj[cur] ){
if( viz == pai ) continue;
nivel[viz] = nivel[cur] + 1;
dfs2( viz, cur );
}
}
int achaPonta( int source ){
nivel[source] = 0;
dfs2( source, source );
pair< int, int > resp( -1, -1 );
for( int i = 0; i < n; i++ ){ resp = max( resp, make_pair( nivel[i], i ) ); }
return resp.second;
}
bool cmp( int a, int b ){ return nivel[a] > nivel[b]; }
int solve( int node ){
nivel[node] = 0;
dfs2( node, node );
sort( vert.begin(), vert.end(), cmp );
int resp = 1;
update(vert[0]);
for( int i = 1; i < n; i++ ){
if( query( vert[i] ) >= d ){
resp++;
update(vert[i]);
}
}
return resp;
}
void init( int n ){
for( int i = 0; i < n; i++ ){
distMin[i] = maxn;
vert.push_back(i);
}
}
int main(){
cin >> n >> d;
init(n);
for( int i = 1; i < n; i++ ){
int x; cin >> x;
adj[i].push_back(x);
adj[x].push_back(i);
}
decompose( 0, -1, 0 );
cout << solve(achaPonta(0));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
4948 KB |
Output is correct |
12 |
Correct |
2 ms |
4948 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
2 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
2 ms |
4948 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
4948 KB |
Output is correct |
12 |
Correct |
2 ms |
4948 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
2 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
2 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
5332 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
3 ms |
5076 KB |
Output is correct |
25 |
Correct |
3 ms |
5076 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
3 ms |
5204 KB |
Output is correct |
29 |
Correct |
3 ms |
5204 KB |
Output is correct |
30 |
Correct |
3 ms |
5204 KB |
Output is correct |
31 |
Correct |
3 ms |
5204 KB |
Output is correct |
32 |
Correct |
3 ms |
5076 KB |
Output is correct |
33 |
Correct |
3 ms |
5076 KB |
Output is correct |
34 |
Correct |
3 ms |
5076 KB |
Output is correct |
35 |
Correct |
3 ms |
5076 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
3 ms |
5204 KB |
Output is correct |
38 |
Correct |
3 ms |
5204 KB |
Output is correct |
39 |
Correct |
3 ms |
5204 KB |
Output is correct |
40 |
Correct |
3 ms |
5332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
3 ms |
4948 KB |
Output is correct |
6 |
Correct |
2 ms |
4948 KB |
Output is correct |
7 |
Correct |
3 ms |
4948 KB |
Output is correct |
8 |
Correct |
2 ms |
4948 KB |
Output is correct |
9 |
Correct |
2 ms |
4948 KB |
Output is correct |
10 |
Correct |
2 ms |
4948 KB |
Output is correct |
11 |
Correct |
2 ms |
4948 KB |
Output is correct |
12 |
Correct |
2 ms |
4948 KB |
Output is correct |
13 |
Correct |
2 ms |
4948 KB |
Output is correct |
14 |
Correct |
2 ms |
4948 KB |
Output is correct |
15 |
Correct |
2 ms |
4948 KB |
Output is correct |
16 |
Correct |
2 ms |
4948 KB |
Output is correct |
17 |
Correct |
2 ms |
4948 KB |
Output is correct |
18 |
Correct |
2 ms |
4948 KB |
Output is correct |
19 |
Correct |
3 ms |
4948 KB |
Output is correct |
20 |
Correct |
2 ms |
4948 KB |
Output is correct |
21 |
Correct |
3 ms |
5332 KB |
Output is correct |
22 |
Correct |
3 ms |
5076 KB |
Output is correct |
23 |
Correct |
3 ms |
5076 KB |
Output is correct |
24 |
Correct |
3 ms |
5076 KB |
Output is correct |
25 |
Correct |
3 ms |
5076 KB |
Output is correct |
26 |
Correct |
3 ms |
5076 KB |
Output is correct |
27 |
Correct |
3 ms |
5076 KB |
Output is correct |
28 |
Correct |
3 ms |
5204 KB |
Output is correct |
29 |
Correct |
3 ms |
5204 KB |
Output is correct |
30 |
Correct |
3 ms |
5204 KB |
Output is correct |
31 |
Correct |
3 ms |
5204 KB |
Output is correct |
32 |
Correct |
3 ms |
5076 KB |
Output is correct |
33 |
Correct |
3 ms |
5076 KB |
Output is correct |
34 |
Correct |
3 ms |
5076 KB |
Output is correct |
35 |
Correct |
3 ms |
5076 KB |
Output is correct |
36 |
Correct |
3 ms |
5076 KB |
Output is correct |
37 |
Correct |
3 ms |
5204 KB |
Output is correct |
38 |
Correct |
3 ms |
5204 KB |
Output is correct |
39 |
Correct |
3 ms |
5204 KB |
Output is correct |
40 |
Correct |
3 ms |
5332 KB |
Output is correct |
41 |
Correct |
85 ms |
18144 KB |
Output is correct |
42 |
Correct |
99 ms |
15732 KB |
Output is correct |
43 |
Correct |
86 ms |
15668 KB |
Output is correct |
44 |
Correct |
99 ms |
15708 KB |
Output is correct |
45 |
Correct |
83 ms |
15572 KB |
Output is correct |
46 |
Correct |
231 ms |
26232 KB |
Output is correct |
47 |
Correct |
235 ms |
26648 KB |
Output is correct |
48 |
Correct |
257 ms |
27188 KB |
Output is correct |
49 |
Correct |
241 ms |
26560 KB |
Output is correct |
50 |
Correct |
58 ms |
14768 KB |
Output is correct |
51 |
Correct |
49 ms |
14984 KB |
Output is correct |
52 |
Correct |
54 ms |
14676 KB |
Output is correct |
53 |
Correct |
141 ms |
24212 KB |
Output is correct |
54 |
Correct |
141 ms |
24256 KB |
Output is correct |
55 |
Correct |
139 ms |
24148 KB |
Output is correct |
56 |
Correct |
4 ms |
5332 KB |
Output is correct |
57 |
Correct |
18 ms |
9020 KB |
Output is correct |
58 |
Correct |
88 ms |
23928 KB |
Output is correct |
59 |
Correct |
269 ms |
37408 KB |
Output is correct |
60 |
Correct |
87 ms |
18548 KB |
Output is correct |
61 |
Correct |
133 ms |
21516 KB |
Output is correct |