#include <bits/stdc++.h>
#define N 100001
#define L 21
using namespace std;
int n, q, root, lg[N];
int par[N][L], mn[N], revord[N];
vector<int> tree[N], ord;
struct comp {
bool operator() (int x, int y) const {
return revord[x] < revord[y];
}
};
set<int, comp> st;
bool vis[N];
int min_dfs(int node) {
int res = node;
for (int child : tree[node]) {
res = min(res, min_dfs(child));
}
return mn[node] = res;
}
void ord_dfs(int node) {
vector<pair<int, int>> w;
for (int child : tree[node]) {
w.push_back(make_pair(mn[child], child));
}
sort(w.begin(), w.end());
for (auto child : w) ord_dfs(child.second);
ord.push_back(node);
revord[node] = ord.size()-1;
}
void fill_par() {
for (int l=1; l<L; l++) {
for (int i=1; i<=n; i++) {
par[i][l] = par[par[i][l-1]][l-1];
}
}
}
int main() {
cin>>n>>q; lg[0] = -1;
for (int i=1; i<=n; i++) {
int p; cin>>p;
if (p == 0) root = i;
tree[p].push_back(i);
par[i][0] = p;
lg[i] = lg[i/2] + 1;
}
min_dfs(root);
ord_dfs(root);
fill_par();
for (int i=1; i<=n; i++) st.insert(i);
while (q--) {
int t; cin>>t;
if (t == 1) {
int k; cin>>k;
while (k--) {
int x = *st.begin();
vis[x] = 1;
if (k == 0) cout<<x<<endl;
st.erase(st.begin());
}
} else {
int x; cin>>x;
int y = x, len = 0;
for (int l=L-1; l>=0; l--) {
if (vis[par[y][l]]) y = par[y][l], len += 1<<l;
}
vis[y] = 0;
st.insert(y);
cout<<len<<endl;
}
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
2688 KB |
Output is correct |
2 |
Correct |
489 ms |
14584 KB |
Output is correct |
3 |
Correct |
408 ms |
14712 KB |
Output is correct |
4 |
Correct |
2 ms |
2688 KB |
Output is correct |
5 |
Correct |
3 ms |
2688 KB |
Output is correct |
6 |
Correct |
5 ms |
2816 KB |
Output is correct |
7 |
Correct |
6 ms |
2816 KB |
Output is correct |
8 |
Correct |
7 ms |
2816 KB |
Output is correct |
9 |
Correct |
34 ms |
3456 KB |
Output is correct |
10 |
Correct |
96 ms |
5632 KB |
Output is correct |
11 |
Correct |
495 ms |
14620 KB |
Output is correct |
12 |
Correct |
407 ms |
14712 KB |
Output is correct |
13 |
Correct |
469 ms |
14584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
272 ms |
8440 KB |
Output is correct |
2 |
Correct |
592 ms |
25580 KB |
Output is correct |
3 |
Correct |
443 ms |
19652 KB |
Output is correct |
4 |
Correct |
353 ms |
10072 KB |
Output is correct |
5 |
Correct |
373 ms |
10208 KB |
Output is correct |
6 |
Correct |
403 ms |
9956 KB |
Output is correct |
7 |
Correct |
347 ms |
8888 KB |
Output is correct |
8 |
Correct |
270 ms |
8440 KB |
Output is correct |
9 |
Correct |
562 ms |
26076 KB |
Output is correct |
10 |
Correct |
584 ms |
25892 KB |
Output is correct |
11 |
Correct |
549 ms |
25892 KB |
Output is correct |
12 |
Correct |
585 ms |
22964 KB |
Output is correct |
13 |
Correct |
489 ms |
28276 KB |
Output is correct |
14 |
Correct |
434 ms |
19560 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
287 ms |
14372 KB |
Output is correct |
2 |
Correct |
621 ms |
22720 KB |
Output is correct |
3 |
Correct |
406 ms |
25720 KB |
Output is correct |
4 |
Correct |
408 ms |
21232 KB |
Output is correct |
5 |
Correct |
398 ms |
21052 KB |
Output is correct |
6 |
Correct |
404 ms |
20900 KB |
Output is correct |
7 |
Correct |
413 ms |
18992 KB |
Output is correct |
8 |
Correct |
403 ms |
25720 KB |
Output is correct |
9 |
Correct |
630 ms |
25700 KB |
Output is correct |
10 |
Correct |
586 ms |
25248 KB |
Output is correct |
11 |
Correct |
621 ms |
25256 KB |
Output is correct |
12 |
Correct |
626 ms |
22884 KB |
Output is correct |
13 |
Correct |
607 ms |
31260 KB |
Output is correct |
14 |
Correct |
536 ms |
19688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
599 ms |
25788 KB |
Output is correct |
2 |
Correct |
609 ms |
22980 KB |
Output is correct |
3 |
Correct |
524 ms |
31220 KB |
Output is correct |
4 |
Correct |
606 ms |
25824 KB |
Output is correct |
5 |
Correct |
605 ms |
25248 KB |
Output is correct |
6 |
Correct |
562 ms |
25348 KB |
Output is correct |
7 |
Correct |
603 ms |
23108 KB |
Output is correct |
8 |
Correct |
506 ms |
31092 KB |
Output is correct |
9 |
Correct |
447 ms |
19688 KB |
Output is correct |