#include <bits/stdc++.h>
using namespace std;
typedef int64_t llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
//#define endl '\n'
int n,d;
int ans=0;
set<int> adj[200001];
int vis[200001];
vector<pair<int,int>> cur;
int par[200001];
void dfs(int no,int par2=-1,int levv=0){
cur.pb({levv,no});
for(auto j:adj[no]){
if(j==par2){
continue;
}
dfs(j,no,levv+1);
}
}
int ss[200001];
void dfs2(int no,int par2=-1,int levv=0){
ss[no]=1;
for(auto j:adj[no]){
if(j==par2){
continue;
}
dfs2(j,no,levv+1);
ss[no]+=ss[j];
}
}
int lo=0;
int find(int no,int par2=-1){
for(auto j:adj[no]){
if(j==par2){
continue;
}
if(ss[j]>lo/2){
return find(j,no);
}
}
return no;
}
/*vector<int> mm;
void dfs2(int no,int par=-1,int levv=0){
vis[no]=1;
mm.pb(no);
// if(levv<d){
for(auto j:adj[no]){
if(j.b==par){
continue;
}
if(j.a+levv>=d){
break;
}
dfs2(j.b,no,levv+j.a);
}
// }
}*/
int cot;
int cot2;
vector<pair<int,int>> dist[200001];
int dist2[200001][20];
int lev[200001];
int ind[200001];
void calc(int no,int par2=-1,int levv=0){
dist2[no][cot2]=levv;
dist[cot].pb({levv,no});
for(auto j:adj[no]){
if(j==par2){
continue;
}
calc(j,no,levv+1);
}
}
void dec(int no,int par2=-1,int levv=0){
if(levv>=20){
while(true){
continue;
}
}
dfs2(no);
lo=ss[no];
int cen=find(no);
//cout<<cen<<","<<levv<<endl;
cot=cen;
cot2=levv;
lev[cen]=levv;
par[cen]=par2;
calc(cen);
sort(dist[cen].begin(),dist[cen].end());
ind[cen]=0;
for(auto j:adj[cen]){
adj[j].erase(cen);
}
for(auto j:adj[cen]){
dec(j,cen,levv+1);
}
adj[cen].clear();
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>d;
for(int i=1;i<n;i++){
int aa;
cin>>aa;
adj[aa].insert(i);
adj[i].insert(aa);
}
dfs(0);
sort(cur.begin(),cur.end());
reverse(cur.begin(),cur.end());
dec(0);
for(auto no:cur){
if(vis[no.b]){
continue;
}
int nn=no.b;
while(nn!=-1){
int x=dist2[no.b][lev[nn]];
while(ind[nn]<dist[nn].size()){
if(dist[nn][ind[nn]].a+x<d){
vis[dist[nn][ind[nn]].b]=1;
ind[nn]+=1;
}
else{
break;
}
}
nn=par[nn];
}
ans+=1;
/*ans+=1;
dfs2(no.b);
for(auto j:mm){
for(auto ll:adj[j]){
if(ll==)
if(adj[ll].find(j)!=adj[ll].end()){
adj[ll].erase(j);
}
}
}
mm.clear();*/
}
cout<<ans<<endl;
return 0;
}
Compilation message
catinatree.cpp: In function 'int main()':
catinatree.cpp:137:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(ind[nn]<dist[nn].size()){
~~~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14464 KB |
Output is correct |
3 |
Correct |
13 ms |
14464 KB |
Output is correct |
4 |
Correct |
13 ms |
14464 KB |
Output is correct |
5 |
Correct |
14 ms |
14464 KB |
Output is correct |
6 |
Correct |
14 ms |
14464 KB |
Output is correct |
7 |
Correct |
14 ms |
14464 KB |
Output is correct |
8 |
Correct |
13 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
13 ms |
14464 KB |
Output is correct |
11 |
Correct |
13 ms |
14512 KB |
Output is correct |
12 |
Correct |
14 ms |
14464 KB |
Output is correct |
13 |
Correct |
13 ms |
14464 KB |
Output is correct |
14 |
Correct |
13 ms |
14464 KB |
Output is correct |
15 |
Correct |
13 ms |
14464 KB |
Output is correct |
16 |
Correct |
13 ms |
14464 KB |
Output is correct |
17 |
Correct |
13 ms |
14464 KB |
Output is correct |
18 |
Correct |
14 ms |
14464 KB |
Output is correct |
19 |
Correct |
13 ms |
14464 KB |
Output is correct |
20 |
Correct |
14 ms |
14464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14464 KB |
Output is correct |
3 |
Correct |
13 ms |
14464 KB |
Output is correct |
4 |
Correct |
13 ms |
14464 KB |
Output is correct |
5 |
Correct |
14 ms |
14464 KB |
Output is correct |
6 |
Correct |
14 ms |
14464 KB |
Output is correct |
7 |
Correct |
14 ms |
14464 KB |
Output is correct |
8 |
Correct |
13 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
13 ms |
14464 KB |
Output is correct |
11 |
Correct |
13 ms |
14512 KB |
Output is correct |
12 |
Correct |
14 ms |
14464 KB |
Output is correct |
13 |
Correct |
13 ms |
14464 KB |
Output is correct |
14 |
Correct |
13 ms |
14464 KB |
Output is correct |
15 |
Correct |
13 ms |
14464 KB |
Output is correct |
16 |
Correct |
13 ms |
14464 KB |
Output is correct |
17 |
Correct |
13 ms |
14464 KB |
Output is correct |
18 |
Correct |
14 ms |
14464 KB |
Output is correct |
19 |
Correct |
13 ms |
14464 KB |
Output is correct |
20 |
Correct |
14 ms |
14464 KB |
Output is correct |
21 |
Correct |
15 ms |
14976 KB |
Output is correct |
22 |
Correct |
15 ms |
14568 KB |
Output is correct |
23 |
Correct |
14 ms |
14592 KB |
Output is correct |
24 |
Correct |
13 ms |
14592 KB |
Output is correct |
25 |
Correct |
14 ms |
14720 KB |
Output is correct |
26 |
Correct |
14 ms |
14720 KB |
Output is correct |
27 |
Correct |
15 ms |
14720 KB |
Output is correct |
28 |
Correct |
15 ms |
14848 KB |
Output is correct |
29 |
Correct |
15 ms |
14848 KB |
Output is correct |
30 |
Correct |
17 ms |
14848 KB |
Output is correct |
31 |
Correct |
15 ms |
14848 KB |
Output is correct |
32 |
Correct |
14 ms |
14848 KB |
Output is correct |
33 |
Correct |
15 ms |
14848 KB |
Output is correct |
34 |
Correct |
14 ms |
14720 KB |
Output is correct |
35 |
Correct |
15 ms |
14848 KB |
Output is correct |
36 |
Correct |
14 ms |
14848 KB |
Output is correct |
37 |
Correct |
16 ms |
14848 KB |
Output is correct |
38 |
Correct |
15 ms |
14848 KB |
Output is correct |
39 |
Correct |
16 ms |
14848 KB |
Output is correct |
40 |
Correct |
15 ms |
14976 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
14464 KB |
Output is correct |
2 |
Correct |
13 ms |
14464 KB |
Output is correct |
3 |
Correct |
13 ms |
14464 KB |
Output is correct |
4 |
Correct |
13 ms |
14464 KB |
Output is correct |
5 |
Correct |
14 ms |
14464 KB |
Output is correct |
6 |
Correct |
14 ms |
14464 KB |
Output is correct |
7 |
Correct |
14 ms |
14464 KB |
Output is correct |
8 |
Correct |
13 ms |
14464 KB |
Output is correct |
9 |
Correct |
15 ms |
14464 KB |
Output is correct |
10 |
Correct |
13 ms |
14464 KB |
Output is correct |
11 |
Correct |
13 ms |
14512 KB |
Output is correct |
12 |
Correct |
14 ms |
14464 KB |
Output is correct |
13 |
Correct |
13 ms |
14464 KB |
Output is correct |
14 |
Correct |
13 ms |
14464 KB |
Output is correct |
15 |
Correct |
13 ms |
14464 KB |
Output is correct |
16 |
Correct |
13 ms |
14464 KB |
Output is correct |
17 |
Correct |
13 ms |
14464 KB |
Output is correct |
18 |
Correct |
14 ms |
14464 KB |
Output is correct |
19 |
Correct |
13 ms |
14464 KB |
Output is correct |
20 |
Correct |
14 ms |
14464 KB |
Output is correct |
21 |
Correct |
15 ms |
14976 KB |
Output is correct |
22 |
Correct |
15 ms |
14568 KB |
Output is correct |
23 |
Correct |
14 ms |
14592 KB |
Output is correct |
24 |
Correct |
13 ms |
14592 KB |
Output is correct |
25 |
Correct |
14 ms |
14720 KB |
Output is correct |
26 |
Correct |
14 ms |
14720 KB |
Output is correct |
27 |
Correct |
15 ms |
14720 KB |
Output is correct |
28 |
Correct |
15 ms |
14848 KB |
Output is correct |
29 |
Correct |
15 ms |
14848 KB |
Output is correct |
30 |
Correct |
17 ms |
14848 KB |
Output is correct |
31 |
Correct |
15 ms |
14848 KB |
Output is correct |
32 |
Correct |
14 ms |
14848 KB |
Output is correct |
33 |
Correct |
15 ms |
14848 KB |
Output is correct |
34 |
Correct |
14 ms |
14720 KB |
Output is correct |
35 |
Correct |
15 ms |
14848 KB |
Output is correct |
36 |
Correct |
14 ms |
14848 KB |
Output is correct |
37 |
Correct |
16 ms |
14848 KB |
Output is correct |
38 |
Correct |
15 ms |
14848 KB |
Output is correct |
39 |
Correct |
16 ms |
14848 KB |
Output is correct |
40 |
Correct |
15 ms |
14976 KB |
Output is correct |
41 |
Correct |
283 ms |
55012 KB |
Output is correct |
42 |
Correct |
399 ms |
41200 KB |
Output is correct |
43 |
Correct |
383 ms |
41456 KB |
Output is correct |
44 |
Correct |
393 ms |
41424 KB |
Output is correct |
45 |
Correct |
440 ms |
41196 KB |
Output is correct |
46 |
Correct |
964 ms |
68120 KB |
Output is correct |
47 |
Correct |
844 ms |
68452 KB |
Output is correct |
48 |
Correct |
843 ms |
68708 KB |
Output is correct |
49 |
Correct |
876 ms |
68836 KB |
Output is correct |
50 |
Correct |
290 ms |
40168 KB |
Output is correct |
51 |
Correct |
299 ms |
40560 KB |
Output is correct |
52 |
Correct |
300 ms |
40172 KB |
Output is correct |
53 |
Correct |
726 ms |
67040 KB |
Output is correct |
54 |
Correct |
716 ms |
66532 KB |
Output is correct |
55 |
Correct |
679 ms |
66788 KB |
Output is correct |
56 |
Correct |
17 ms |
15232 KB |
Output is correct |
57 |
Correct |
57 ms |
22260 KB |
Output is correct |
58 |
Correct |
272 ms |
50028 KB |
Output is correct |
59 |
Correct |
818 ms |
82396 KB |
Output is correct |
60 |
Correct |
292 ms |
56288 KB |
Output is correct |
61 |
Correct |
397 ms |
55652 KB |
Output is correct |