#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;
par[nxt][0] = now;
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);
int C = 0;
while(Q--){
int t,k;
cin>>t>>k;
int lst = 0;
//assert(C == N-st.size());
if(t == 1){
C += k;
while(k--){
lst = eul[*st.begin()];
st.erase(*st.begin());
dp[lst] = 1;
}
cout<<lst<<'\n';
}
else{
C--;
lst = k;
for(int i = 19;i>=0;i--){
if(dp[par[lst][i]])lst = par[lst][i];
}
dp[lst] = false;
assert(st.find(dfn[lst]) == st.end());
st.insert(dfn[lst]);
cout<<dep[k]-dep[lst]<<'\n';
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
4 ms |
5464 KB |
Execution killed with signal 6 |
2 |
Runtime error |
39 ms |
26224 KB |
Execution killed with signal 6 |
3 |
Runtime error |
37 ms |
25544 KB |
Execution killed with signal 6 |
4 |
Runtime error |
4 ms |
5212 KB |
Execution killed with signal 6 |
5 |
Runtime error |
4 ms |
5468 KB |
Execution killed with signal 6 |
6 |
Runtime error |
4 ms |
5724 KB |
Execution killed with signal 6 |
7 |
Runtime error |
5 ms |
5704 KB |
Execution killed with signal 6 |
8 |
Runtime error |
4 ms |
5724 KB |
Execution killed with signal 6 |
9 |
Runtime error |
5 ms |
6748 KB |
Execution killed with signal 6 |
10 |
Runtime error |
12 ms |
10588 KB |
Execution killed with signal 6 |
11 |
Runtime error |
38 ms |
26220 KB |
Execution killed with signal 6 |
12 |
Runtime error |
46 ms |
25636 KB |
Execution killed with signal 6 |
13 |
Runtime error |
36 ms |
26064 KB |
Execution killed with signal 6 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
7252 KB |
Output is correct |
2 |
Runtime error |
74 ms |
44228 KB |
Execution killed with signal 6 |
3 |
Runtime error |
73 ms |
35808 KB |
Execution killed with signal 6 |
4 |
Runtime error |
21 ms |
17240 KB |
Execution killed with signal 6 |
5 |
Runtime error |
19 ms |
16988 KB |
Execution killed with signal 6 |
6 |
Runtime error |
20 ms |
16884 KB |
Execution killed with signal 6 |
7 |
Runtime error |
20 ms |
15196 KB |
Execution killed with signal 6 |
8 |
Correct |
29 ms |
7252 KB |
Output is correct |
9 |
Runtime error |
69 ms |
45004 KB |
Execution killed with signal 6 |
10 |
Runtime error |
95 ms |
44256 KB |
Execution killed with signal 6 |
11 |
Runtime error |
71 ms |
43984 KB |
Execution killed with signal 6 |
12 |
Runtime error |
88 ms |
40136 KB |
Execution killed with signal 6 |
13 |
Correct |
82 ms |
23444 KB |
Output is correct |
14 |
Runtime error |
60 ms |
35672 KB |
Execution killed with signal 6 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
52 ms |
12672 KB |
Output isn't correct |
2 |
Runtime error |
75 ms |
40968 KB |
Execution killed with signal 6 |
3 |
Correct |
98 ms |
21788 KB |
Output is correct |
4 |
Runtime error |
59 ms |
37064 KB |
Execution killed with signal 6 |
5 |
Runtime error |
80 ms |
36364 KB |
Execution killed with signal 6 |
6 |
Runtime error |
57 ms |
36304 KB |
Execution killed with signal 6 |
7 |
Runtime error |
54 ms |
33744 KB |
Execution killed with signal 6 |
8 |
Correct |
90 ms |
21752 KB |
Output is correct |
9 |
Runtime error |
145 ms |
45280 KB |
Execution killed with signal 6 |
10 |
Runtime error |
119 ms |
44496 KB |
Execution killed with signal 6 |
11 |
Runtime error |
107 ms |
44240 KB |
Execution killed with signal 6 |
12 |
Runtime error |
73 ms |
40904 KB |
Execution killed with signal 6 |
13 |
Correct |
157 ms |
26828 KB |
Output is correct |
14 |
Runtime error |
75 ms |
36556 KB |
Execution killed with signal 6 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
70 ms |
44980 KB |
Execution killed with signal 6 |
2 |
Runtime error |
71 ms |
40908 KB |
Execution killed with signal 6 |
3 |
Correct |
119 ms |
26244 KB |
Output is correct |
4 |
Runtime error |
81 ms |
45316 KB |
Execution killed with signal 6 |
5 |
Runtime error |
74 ms |
44244 KB |
Execution killed with signal 6 |
6 |
Runtime error |
70 ms |
44240 KB |
Execution killed with signal 6 |
7 |
Runtime error |
80 ms |
40908 KB |
Execution killed with signal 6 |
8 |
Correct |
94 ms |
26140 KB |
Output is correct |
9 |
Runtime error |
63 ms |
36116 KB |
Execution killed with signal 6 |