#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+7;
const int LOG = 19;
int jp[MAXN][LOG];
int ojciec[MAXN];
int depth[MAXN];
int post[MAXN];
bool ball[MAXN];
vector<int> g[MAXN];
set<pair<int,int> > s;
int cnt=0;
void DFS(int x){
depth[x]=depth[ojciec[x]]+1;
jp[x][0]=ojciec[x];
for(int i=1;i<LOG;i++) jp[x][i]=jp[jp[x][i-1]][i-1];
for(int i=0;i<g[x].size();i++){
DFS(g[x][i]);
}
s.insert({++cnt,x});
post[x]=cnt;
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n,q,x,r,a,b;
pair<int,int> p;
cin>>n>>q;
for(int i=1;i<=n;i++){
cin>>x;
ojciec[i]=x;
if(x==0) r=i;
else g[x].push_back(i);
}
DFS(r);
while(q--){
cin>>a>>b;
if(a==1){
while(b--){
auto it=s.begin();
s.erase(it);
p=*it;
ball[p.second]=1;
if(b==0){
cout<<p.second<<'\n';
}
}
}
else{
x=b;
while(x>0){
if(ball[ojciec[x]]) x=ojciec[x];
else break;
}
ball[x]=0;
s.insert({post[x],x});
//cout<<b<<' '<<x<<'\n';
cout<<depth[b]-depth[x]<<'\n';
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void DFS(int)':
ballmachine.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | for(int i=0;i<g[x].size();i++){
| ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:34:5: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
34 | DFS(r);
| ~~~^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
4700 KB |
Output isn't correct |
| 2 |
Execution timed out |
1095 ms |
15028 KB |
Time limit exceeded |
| 3 |
Incorrect |
59 ms |
15444 KB |
Output isn't correct |
| 4 |
Execution timed out |
1076 ms |
4700 KB |
Time limit exceeded |
| 5 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 6 |
Incorrect |
1 ms |
4700 KB |
Output isn't correct |
| 7 |
Execution timed out |
1054 ms |
4700 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1069 ms |
4700 KB |
Time limit exceeded |
| 9 |
Incorrect |
4 ms |
4952 KB |
Output isn't correct |
| 10 |
Execution timed out |
1050 ms |
7772 KB |
Time limit exceeded |
| 11 |
Incorrect |
65 ms |
15064 KB |
Output isn't correct |
| 12 |
Incorrect |
44 ms |
15184 KB |
Output isn't correct |
| 13 |
Incorrect |
54 ms |
14936 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
21 ms |
9556 KB |
Output is correct |
| 2 |
Execution timed out |
1022 ms |
21556 KB |
Time limit exceeded |
| 3 |
Incorrect |
52 ms |
17692 KB |
Output isn't correct |
| 4 |
Execution timed out |
1078 ms |
9820 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1068 ms |
9564 KB |
Time limit exceeded |
| 6 |
Incorrect |
99 ms |
9820 KB |
Output isn't correct |
| 7 |
Incorrect |
54 ms |
9160 KB |
Output isn't correct |
| 8 |
Correct |
21 ms |
9564 KB |
Output is correct |
| 9 |
Incorrect |
73 ms |
21976 KB |
Output isn't correct |
| 10 |
Execution timed out |
1050 ms |
21644 KB |
Time limit exceeded |
| 11 |
Incorrect |
86 ms |
21332 KB |
Output isn't correct |
| 12 |
Incorrect |
279 ms |
20116 KB |
Output isn't correct |
| 13 |
Correct |
58 ms |
23636 KB |
Output is correct |
| 14 |
Incorrect |
64 ms |
17856 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
724 ms |
14236 KB |
Output isn't correct |
| 2 |
Execution timed out |
1061 ms |
20036 KB |
Time limit exceeded |
| 3 |
Execution timed out |
1047 ms |
22164 KB |
Time limit exceeded |
| 4 |
Execution timed out |
1051 ms |
19300 KB |
Time limit exceeded |
| 5 |
Incorrect |
871 ms |
19020 KB |
Output isn't correct |
| 6 |
Incorrect |
866 ms |
18952 KB |
Output isn't correct |
| 7 |
Incorrect |
575 ms |
17648 KB |
Output isn't correct |
| 8 |
Execution timed out |
1068 ms |
22188 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1045 ms |
21932 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1034 ms |
21072 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1056 ms |
21324 KB |
Time limit exceeded |
| 12 |
Execution timed out |
1054 ms |
19976 KB |
Time limit exceeded |
| 13 |
Execution timed out |
1008 ms |
25680 KB |
Time limit exceeded |
| 14 |
Incorrect |
77 ms |
17612 KB |
Output isn't correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
1068 ms |
22084 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1039 ms |
20288 KB |
Time limit exceeded |
| 3 |
Correct |
80 ms |
25940 KB |
Output is correct |
| 4 |
Execution timed out |
1032 ms |
21852 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1008 ms |
21596 KB |
Time limit exceeded |
| 6 |
Incorrect |
146 ms |
21528 KB |
Output isn't correct |
| 7 |
Execution timed out |
1058 ms |
19964 KB |
Time limit exceeded |
| 8 |
Correct |
70 ms |
25940 KB |
Output is correct |
| 9 |
Incorrect |
58 ms |
17616 KB |
Output isn't correct |
