#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];
int sm[mxn];
set<int> st;
void dfs(int now){
sm[now] = now;
for(int i = 1;i<20;i++)par[now][i] = par[par[now][i-1]][i-1];
for(auto nxt:tree[now]){
dep[nxt] = dep[now]+1;
dfs(nxt);
sm[now] = min(sm[now],sm[nxt]);
}
return;
}
void dfs1(int now){
sort(tree[now].begin(),tree[now].end(),[](int a,int b){return sm[a]<sm[b];});
for(auto nxt:tree[now])dfs1(nxt);
dfn[now] = eul.size();
eul.push_back(now);
}
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);
dfs1(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;
assert(dp[k]);
for(int i = 19;i>=0;i--){
if(dp[par[lst][i]])lst = par[lst][i];
}
st.insert(dfn[lst]);
dp[lst] = 0;
cout<<dep[k]-dep[lst]<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
5720 KB |
Output is correct |
| 2 |
Correct |
89 ms |
16680 KB |
Output is correct |
| 3 |
Correct |
52 ms |
16856 KB |
Output is correct |
| 4 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 5 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 6 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 7 |
Correct |
2 ms |
5724 KB |
Output is correct |
| 8 |
Correct |
2 ms |
5720 KB |
Output is correct |
| 9 |
Correct |
6 ms |
6232 KB |
Output is correct |
| 10 |
Correct |
20 ms |
9048 KB |
Output is correct |
| 11 |
Correct |
106 ms |
16768 KB |
Output is correct |
| 12 |
Correct |
52 ms |
16744 KB |
Output is correct |
| 13 |
Correct |
77 ms |
16660 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
28 ms |
10840 KB |
Output is correct |
| 2 |
Correct |
130 ms |
22384 KB |
Output is correct |
| 3 |
Correct |
77 ms |
18656 KB |
Output is correct |
| 4 |
Correct |
58 ms |
11348 KB |
Output is correct |
| 5 |
Correct |
61 ms |
11168 KB |
Output is correct |
| 6 |
Correct |
54 ms |
11184 KB |
Output is correct |
| 7 |
Correct |
56 ms |
10480 KB |
Output is correct |
| 8 |
Correct |
29 ms |
10832 KB |
Output is correct |
| 9 |
Correct |
148 ms |
22904 KB |
Output is correct |
| 10 |
Correct |
139 ms |
22400 KB |
Output is correct |
| 11 |
Correct |
114 ms |
22524 KB |
Output is correct |
| 12 |
Correct |
119 ms |
20604 KB |
Output is correct |
| 13 |
Correct |
82 ms |
25544 KB |
Output is correct |
| 14 |
Correct |
75 ms |
18676 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
70 ms |
15508 KB |
Output is correct |
| 2 |
Correct |
150 ms |
21080 KB |
Output is correct |
| 3 |
Correct |
95 ms |
24044 KB |
Output is correct |
| 4 |
Correct |
84 ms |
20680 KB |
Output is correct |
| 5 |
Correct |
89 ms |
20432 KB |
Output is correct |
| 6 |
Correct |
95 ms |
20520 KB |
Output is correct |
| 7 |
Correct |
90 ms |
19108 KB |
Output is correct |
| 8 |
Correct |
91 ms |
24016 KB |
Output is correct |
| 9 |
Correct |
154 ms |
23056 KB |
Output is correct |
| 10 |
Correct |
145 ms |
22476 KB |
Output is correct |
| 11 |
Correct |
136 ms |
22680 KB |
Output is correct |
| 12 |
Correct |
139 ms |
20948 KB |
Output is correct |
| 13 |
Correct |
146 ms |
27060 KB |
Output is correct |
| 14 |
Correct |
104 ms |
18632 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
23044 KB |
Output is correct |
| 2 |
Correct |
162 ms |
21196 KB |
Output is correct |
| 3 |
Correct |
107 ms |
26928 KB |
Output is correct |
| 4 |
Correct |
137 ms |
23144 KB |
Output is correct |
| 5 |
Correct |
178 ms |
22508 KB |
Output is correct |
| 6 |
Correct |
116 ms |
22480 KB |
Output is correct |
| 7 |
Correct |
142 ms |
21136 KB |
Output is correct |
| 8 |
Correct |
102 ms |
26828 KB |
Output is correct |
| 9 |
Correct |
69 ms |
18804 KB |
Output is correct |
