#include<bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
int root,n,q,i,j,type,x,a[100005],jump[100005][20],dist[100005];
vector<int> v[100005];
bitset<100005> ball;
void dfs(int k){
a[k]=k;
for(int i:v[k]){
dist[i]=dist[k]+1;
dfs(i);
a[k]=min(a[k],a[i]);
}
}
int find(int x){
if(ball[jump[x][0]]==0) return x;
return find(jump[x][0]);
}
int update(int x){
int mx=1e8,idx=0;
for(int i:v[x]){
if(a[i]<mx && !ball[i]){
mx=a[i];
idx=i;
}
}
if(idx!=0) return update(idx);
else{
ball[x]=1;
return x;
}
}
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin >> n >> q;
for(i=1;i<=n;i++){
cin >> jump[i][0];
if(jump[i][0]==0) root=i;
else v[jump[i][0]].push_back(i);
}
dfs(root);
while(q--){
cin >> type >> x;
if(type==1){
for(i=1;i<=x;i++){
type=update(root);
}
cout << type << "\n";
}
else{
type=find(x);
ball[type]=0;
cout << dist[x]-dist[type] << "\n";
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
4700 KB |
Output is correct |
2 |
Correct |
51 ms |
11276 KB |
Output is correct |
3 |
Correct |
32 ms |
11348 KB |
Output is correct |
4 |
Correct |
1 ms |
4700 KB |
Output is correct |
5 |
Correct |
1 ms |
4700 KB |
Output is correct |
6 |
Correct |
1 ms |
4700 KB |
Output is correct |
7 |
Correct |
1 ms |
4700 KB |
Output is correct |
8 |
Correct |
1 ms |
4700 KB |
Output is correct |
9 |
Correct |
3 ms |
4700 KB |
Output is correct |
10 |
Correct |
11 ms |
5208 KB |
Output is correct |
11 |
Correct |
42 ms |
11348 KB |
Output is correct |
12 |
Correct |
31 ms |
11348 KB |
Output is correct |
13 |
Correct |
41 ms |
11344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1053 ms |
6748 KB |
Time limit exceeded |
2 |
Execution timed out |
1053 ms |
16984 KB |
Time limit exceeded |
3 |
Execution timed out |
1066 ms |
13936 KB |
Time limit exceeded |
4 |
Execution timed out |
1071 ms |
8796 KB |
Time limit exceeded |
5 |
Execution timed out |
1095 ms |
8536 KB |
Time limit exceeded |
6 |
Execution timed out |
1073 ms |
8540 KB |
Time limit exceeded |
7 |
Execution timed out |
1038 ms |
8024 KB |
Time limit exceeded |
8 |
Execution timed out |
1014 ms |
6744 KB |
Time limit exceeded |
9 |
Execution timed out |
1055 ms |
17500 KB |
Time limit exceeded |
10 |
Execution timed out |
1037 ms |
16984 KB |
Time limit exceeded |
11 |
Execution timed out |
1057 ms |
16988 KB |
Time limit exceeded |
12 |
Execution timed out |
1010 ms |
15448 KB |
Time limit exceeded |
13 |
Execution timed out |
1042 ms |
20252 KB |
Time limit exceeded |
14 |
Execution timed out |
1049 ms |
14016 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1010 ms |
12112 KB |
Time limit exceeded |
2 |
Execution timed out |
1031 ms |
15612 KB |
Time limit exceeded |
3 |
Execution timed out |
1051 ms |
19156 KB |
Time limit exceeded |
4 |
Execution timed out |
1055 ms |
16220 KB |
Time limit exceeded |
5 |
Execution timed out |
1070 ms |
15708 KB |
Time limit exceeded |
6 |
Execution timed out |
1012 ms |
15704 KB |
Time limit exceeded |
7 |
Execution timed out |
1086 ms |
14676 KB |
Time limit exceeded |
8 |
Execution timed out |
1061 ms |
19292 KB |
Time limit exceeded |
9 |
Execution timed out |
1052 ms |
17500 KB |
Time limit exceeded |
10 |
Execution timed out |
1063 ms |
17244 KB |
Time limit exceeded |
11 |
Execution timed out |
1054 ms |
17164 KB |
Time limit exceeded |
12 |
Execution timed out |
1040 ms |
15452 KB |
Time limit exceeded |
13 |
Execution timed out |
1047 ms |
21340 KB |
Time limit exceeded |
14 |
Execution timed out |
1051 ms |
13528 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1028 ms |
17496 KB |
Time limit exceeded |
2 |
Execution timed out |
1040 ms |
15448 KB |
Time limit exceeded |
3 |
Execution timed out |
1055 ms |
21524 KB |
Time limit exceeded |
4 |
Execution timed out |
1055 ms |
17496 KB |
Time limit exceeded |
5 |
Execution timed out |
1038 ms |
17240 KB |
Time limit exceeded |
6 |
Execution timed out |
1051 ms |
17244 KB |
Time limit exceeded |
7 |
Execution timed out |
1020 ms |
15448 KB |
Time limit exceeded |
8 |
Execution timed out |
1035 ms |
21684 KB |
Time limit exceeded |
9 |
Execution timed out |
1004 ms |
13940 KB |
Time limit exceeded |