# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
486332 | 2021-11-11T09:44:03 Z | Koosha_mv | Cat in a tree (BOI17_catinatree) | C++14 | 205 ms | 21188 KB |
#include <bits/stdc++.h> using namespace std; #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define Add(x,y) x=(x+y)%mod #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first const int N=2e5+99; int n,t,d,ans,a[N],h[N],mark[N],dist[N]; vector<int> v,g[N]; bool cmp(int i,int j){ return h[i]>h[j]; } void dfs1(int x,int par){ v.pb(x); f(i,0,g[x].size()){ if(g[x][i]!=par){ h[g[x][i]]=h[x]+1; dfs1(g[x][i],x); } } } void dfs2(int x,int par,int d){ if(dist[x]<=d) return ; dist[x]=d; f(i,0,g[x].size()){ if(g[x][i]!=par){ dfs2(g[x][i],x,d+1); } } } int main(){ cin>>n>>d; f(i,1,n){ int x; cin>>x; g[i].pb(x); g[x].pb(i); } dfs1(1,n); fill(dist,dist+N,d); sort(v.begin(),v.end(),cmp); f(i,0,v.size()){ int u=v[i]; if(dist[u]==d){ ans++; dfs2(u,n,0); } } cout<<ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5708 KB | Output is correct |
2 | Correct | 3 ms | 5708 KB | Output is correct |
3 | Correct | 3 ms | 5708 KB | Output is correct |
4 | Correct | 3 ms | 5708 KB | Output is correct |
5 | Correct | 3 ms | 5708 KB | Output is correct |
6 | Correct | 3 ms | 5708 KB | Output is correct |
7 | Correct | 3 ms | 5760 KB | Output is correct |
8 | Correct | 3 ms | 5708 KB | Output is correct |
9 | Correct | 3 ms | 5708 KB | Output is correct |
10 | Correct | 3 ms | 5708 KB | Output is correct |
11 | Correct | 3 ms | 5708 KB | Output is correct |
12 | Correct | 3 ms | 5708 KB | Output is correct |
13 | Correct | 3 ms | 5708 KB | Output is correct |
14 | Correct | 4 ms | 5708 KB | Output is correct |
15 | Correct | 3 ms | 5708 KB | Output is correct |
16 | Correct | 3 ms | 5708 KB | Output is correct |
17 | Correct | 3 ms | 5708 KB | Output is correct |
18 | Correct | 4 ms | 5708 KB | Output is correct |
19 | Correct | 3 ms | 5708 KB | Output is correct |
20 | Correct | 4 ms | 5708 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5708 KB | Output is correct |
2 | Correct | 3 ms | 5708 KB | Output is correct |
3 | Correct | 3 ms | 5708 KB | Output is correct |
4 | Correct | 3 ms | 5708 KB | Output is correct |
5 | Correct | 3 ms | 5708 KB | Output is correct |
6 | Correct | 3 ms | 5708 KB | Output is correct |
7 | Correct | 3 ms | 5760 KB | Output is correct |
8 | Correct | 3 ms | 5708 KB | Output is correct |
9 | Correct | 3 ms | 5708 KB | Output is correct |
10 | Correct | 3 ms | 5708 KB | Output is correct |
11 | Correct | 3 ms | 5708 KB | Output is correct |
12 | Correct | 3 ms | 5708 KB | Output is correct |
13 | Correct | 3 ms | 5708 KB | Output is correct |
14 | Correct | 4 ms | 5708 KB | Output is correct |
15 | Correct | 3 ms | 5708 KB | Output is correct |
16 | Correct | 3 ms | 5708 KB | Output is correct |
17 | Correct | 3 ms | 5708 KB | Output is correct |
18 | Correct | 4 ms | 5708 KB | Output is correct |
19 | Correct | 3 ms | 5708 KB | Output is correct |
20 | Correct | 4 ms | 5708 KB | Output is correct |
21 | Correct | 3 ms | 5836 KB | Output is correct |
22 | Correct | 3 ms | 5708 KB | Output is correct |
23 | Correct | 5 ms | 5836 KB | Output is correct |
24 | Correct | 3 ms | 5824 KB | Output is correct |
25 | Correct | 3 ms | 5708 KB | Output is correct |
26 | Correct | 3 ms | 5836 KB | Output is correct |
27 | Correct | 3 ms | 5832 KB | Output is correct |
28 | Correct | 4 ms | 5836 KB | Output is correct |
29 | Correct | 3 ms | 5836 KB | Output is correct |
30 | Correct | 3 ms | 5836 KB | Output is correct |
31 | Correct | 4 ms | 5836 KB | Output is correct |
32 | Correct | 3 ms | 5836 KB | Output is correct |
33 | Correct | 3 ms | 5836 KB | Output is correct |
34 | Correct | 3 ms | 5836 KB | Output is correct |
35 | Correct | 3 ms | 5836 KB | Output is correct |
36 | Correct | 3 ms | 5836 KB | Output is correct |
37 | Correct | 4 ms | 5836 KB | Output is correct |
38 | Correct | 4 ms | 5836 KB | Output is correct |
39 | Correct | 3 ms | 5836 KB | Output is correct |
40 | Correct | 4 ms | 5928 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 5708 KB | Output is correct |
2 | Correct | 3 ms | 5708 KB | Output is correct |
3 | Correct | 3 ms | 5708 KB | Output is correct |
4 | Correct | 3 ms | 5708 KB | Output is correct |
5 | Correct | 3 ms | 5708 KB | Output is correct |
6 | Correct | 3 ms | 5708 KB | Output is correct |
7 | Correct | 3 ms | 5760 KB | Output is correct |
8 | Correct | 3 ms | 5708 KB | Output is correct |
9 | Correct | 3 ms | 5708 KB | Output is correct |
10 | Correct | 3 ms | 5708 KB | Output is correct |
11 | Correct | 3 ms | 5708 KB | Output is correct |
12 | Correct | 3 ms | 5708 KB | Output is correct |
13 | Correct | 3 ms | 5708 KB | Output is correct |
14 | Correct | 4 ms | 5708 KB | Output is correct |
15 | Correct | 3 ms | 5708 KB | Output is correct |
16 | Correct | 3 ms | 5708 KB | Output is correct |
17 | Correct | 3 ms | 5708 KB | Output is correct |
18 | Correct | 4 ms | 5708 KB | Output is correct |
19 | Correct | 3 ms | 5708 KB | Output is correct |
20 | Correct | 4 ms | 5708 KB | Output is correct |
21 | Correct | 3 ms | 5836 KB | Output is correct |
22 | Correct | 3 ms | 5708 KB | Output is correct |
23 | Correct | 5 ms | 5836 KB | Output is correct |
24 | Correct | 3 ms | 5824 KB | Output is correct |
25 | Correct | 3 ms | 5708 KB | Output is correct |
26 | Correct | 3 ms | 5836 KB | Output is correct |
27 | Correct | 3 ms | 5832 KB | Output is correct |
28 | Correct | 4 ms | 5836 KB | Output is correct |
29 | Correct | 3 ms | 5836 KB | Output is correct |
30 | Correct | 3 ms | 5836 KB | Output is correct |
31 | Correct | 4 ms | 5836 KB | Output is correct |
32 | Correct | 3 ms | 5836 KB | Output is correct |
33 | Correct | 3 ms | 5836 KB | Output is correct |
34 | Correct | 3 ms | 5836 KB | Output is correct |
35 | Correct | 3 ms | 5836 KB | Output is correct |
36 | Correct | 3 ms | 5836 KB | Output is correct |
37 | Correct | 4 ms | 5836 KB | Output is correct |
38 | Correct | 4 ms | 5836 KB | Output is correct |
39 | Correct | 3 ms | 5836 KB | Output is correct |
40 | Correct | 4 ms | 5928 KB | Output is correct |
41 | Correct | 92 ms | 13640 KB | Output is correct |
42 | Correct | 55 ms | 10428 KB | Output is correct |
43 | Correct | 81 ms | 10468 KB | Output is correct |
44 | Correct | 54 ms | 10448 KB | Output is correct |
45 | Correct | 56 ms | 10388 KB | Output is correct |
46 | Correct | 132 ms | 15068 KB | Output is correct |
47 | Correct | 205 ms | 15012 KB | Output is correct |
48 | Correct | 141 ms | 15028 KB | Output is correct |
49 | Correct | 144 ms | 15000 KB | Output is correct |
50 | Correct | 41 ms | 10648 KB | Output is correct |
51 | Correct | 44 ms | 10692 KB | Output is correct |
52 | Correct | 49 ms | 10700 KB | Output is correct |
53 | Correct | 86 ms | 15432 KB | Output is correct |
54 | Correct | 90 ms | 15544 KB | Output is correct |
55 | Correct | 98 ms | 15544 KB | Output is correct |
56 | Correct | 4 ms | 5900 KB | Output is correct |
57 | Correct | 15 ms | 8012 KB | Output is correct |
58 | Correct | 54 ms | 15960 KB | Output is correct |
59 | Correct | 141 ms | 21188 KB | Output is correct |
60 | Correct | 95 ms | 14652 KB | Output is correct |
61 | Correct | 139 ms | 14516 KB | Output is correct |