#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 1e5+10;
vector<int> tree[mxn];
vector<int> eul;
int par[mxn][20],dep[mxn];
int N,Q;
int rt;
int dp[mxn];
int dfn[mxn];
set<int> st;
void dfs(int now){
for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
sort(tree[now].begin(),tree[now].end());
for(auto nxt:tree[now]){
dep[nxt] = dep[now]+1;
dfs(nxt);
}
dfn[now] = eul.size();
eul.push_back(now);
return;
}
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N>>Q;
for(int i = 1;i<=N;i++){
int p;
cin>>p;
par[i][0] = p;
tree[p].push_back(i);
if(!p)rt = i;
}
par[rt][0] = rt;
dfs(rt);
for(int i = 0;i<N;i++)st.insert(i);
while(Q--){
int t,k;
cin>>t>>k;
int lst = 0;
if(t == 1){
while(k--){
lst = *st.begin();
st.erase(st.begin());
dp[lst] = 1;
}
cout<<eul[lst]<<'\n';
}
else{
lst = k;
for(int i = 19;i>=0;i--){
if(dp[par[lst][i]])lst = par[lst][i];
}
dp[lst] = 0;
st.insert(dfn[lst]);
cout<<dep[k]-dep[lst]<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1061 ms |
5468 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1044 ms |
15232 KB |
Time limit exceeded |
| 3 |
Incorrect |
59 ms |
15312 KB |
Output isn't correct |
| 4 |
Execution timed out |
1054 ms |
5468 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1056 ms |
5468 KB |
Time limit exceeded |
| 6 |
Incorrect |
2 ms |
5468 KB |
Output isn't correct |
| 7 |
Execution timed out |
1091 ms |
5468 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1043 ms |
5464 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1066 ms |
5724 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1064 ms |
8928 KB |
Time limit exceeded |
| 11 |
Incorrect |
83 ms |
15312 KB |
Output isn't correct |
| 12 |
Incorrect |
54 ms |
15276 KB |
Output isn't correct |
| 13 |
Incorrect |
67 ms |
15312 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
11032 KB |
Output is correct |
| 2 |
Incorrect |
127 ms |
23456 KB |
Output isn't correct |
| 3 |
Incorrect |
72 ms |
19404 KB |
Output isn't correct |
| 4 |
Execution timed out |
1077 ms |
11352 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1046 ms |
11040 KB |
Time limit exceeded |
| 6 |
Incorrect |
53 ms |
11556 KB |
Output isn't correct |
| 7 |
Incorrect |
52 ms |
10832 KB |
Output isn't correct |
| 8 |
Correct |
28 ms |
10840 KB |
Output is correct |
| 9 |
Incorrect |
107 ms |
23756 KB |
Output isn't correct |
| 10 |
Incorrect |
128 ms |
23508 KB |
Output isn't correct |
| 11 |
Incorrect |
108 ms |
23508 KB |
Output isn't correct |
| 12 |
Incorrect |
121 ms |
21632 KB |
Output isn't correct |
| 13 |
Correct |
78 ms |
25996 KB |
Output is correct |
| 14 |
Incorrect |
66 ms |
19664 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
15832 KB |
Output isn't correct |
| 2 |
Incorrect |
140 ms |
21972 KB |
Output isn't correct |
| 3 |
Incorrect |
96 ms |
24440 KB |
Output isn't correct |
| 4 |
Incorrect |
84 ms |
21400 KB |
Output isn't correct |
| 5 |
Incorrect |
99 ms |
20984 KB |
Output isn't correct |
| 6 |
Incorrect |
85 ms |
20936 KB |
Output isn't correct |
| 7 |
Incorrect |
89 ms |
19740 KB |
Output isn't correct |
| 8 |
Incorrect |
107 ms |
24596 KB |
Output isn't correct |
| 9 |
Incorrect |
151 ms |
24092 KB |
Output isn't correct |
| 10 |
Incorrect |
135 ms |
23656 KB |
Output isn't correct |
| 11 |
Incorrect |
133 ms |
23504 KB |
Output isn't correct |
| 12 |
Incorrect |
142 ms |
22224 KB |
Output isn't correct |
| 13 |
Incorrect |
138 ms |
28104 KB |
Output isn't correct |
| 14 |
Incorrect |
109 ms |
19660 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1037 ms |
23808 KB |
Time limit exceeded |
| 2 |
Incorrect |
160 ms |
21968 KB |
Output isn't correct |
| 3 |
Correct |
120 ms |
27596 KB |
Output is correct |
| 4 |
Execution timed out |
1056 ms |
24040 KB |
Time limit exceeded |
| 5 |
Incorrect |
133 ms |
23504 KB |
Output isn't correct |
| 6 |
Incorrect |
118 ms |
23532 KB |
Output isn't correct |
| 7 |
Incorrect |
153 ms |
22080 KB |
Output isn't correct |
| 8 |
Correct |
86 ms |
27596 KB |
Output is correct |
| 9 |
Incorrect |
61 ms |
19400 KB |
Output isn't correct |
