#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e5 + 5;
const ll linf = 1e18;
const int mod = 1e9 + 7;
vector<int> g[N];
int lift[N][17], mn[N], order[N], out[N], tsz;
void Dfs(int s, int e) {
mn[s] = s;
lift[s][0] = e;
for (int i = 1; i < 17; i++) lift[s][i] = lift[lift[s][i - 1]][i - 1];
for (int u : g[s]) {
if (u != e) {
Dfs(u, s);
smin(mn[s], mn[u]);
}
}
}
void Dfs1(int s, int e) {
for (int u : g[s]) {
if (u != e) {
Dfs1(u, s);
}
}
out[s] = ++tsz;
order[tsz] = s;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, q;
cin >> n >> q;
int root = 0;
for (int i = 1; i <= n; i++) {
int x; cin >> x;
if (x == 0) root = i;
else g[x].push_back(i);
}
Dfs(root, 0);
for (int i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end(), [&] (int xx, int yy) {
return mn[xx] < mn[yy];
});
}
Dfs1(root, 0);
set<int> s;
for (int i = 1; i <= n; i++) s.insert(i);
while (q--) {
int ty, x;
cin >> ty >> x;
if (ty == 1) {
int res = -1;
while (x--) {
res = *s.begin();
s.erase(res);
}
cout << order[res] << en;
continue;
}
int ans = 0;
for (int i = 16; i >= 0; i--) {
int who = lift[x][i];
if (s.find(out[who]) == s.end() && who > 0) {
ans += 1 << i;
x = who;
}
}
s.insert(out[x]);
cout << ans << en;
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2644 KB |
Output is correct |
2 |
Correct |
157 ms |
13188 KB |
Output is correct |
3 |
Correct |
82 ms |
13252 KB |
Output is correct |
4 |
Correct |
2 ms |
2656 KB |
Output is correct |
5 |
Correct |
2 ms |
2680 KB |
Output is correct |
6 |
Correct |
2 ms |
2772 KB |
Output is correct |
7 |
Correct |
3 ms |
2772 KB |
Output is correct |
8 |
Correct |
3 ms |
2812 KB |
Output is correct |
9 |
Correct |
9 ms |
3284 KB |
Output is correct |
10 |
Correct |
27 ms |
5236 KB |
Output is correct |
11 |
Correct |
161 ms |
13184 KB |
Output is correct |
12 |
Correct |
74 ms |
13196 KB |
Output is correct |
13 |
Correct |
136 ms |
13200 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
43 ms |
7656 KB |
Output is correct |
2 |
Correct |
309 ms |
22712 KB |
Output is correct |
3 |
Correct |
111 ms |
17608 KB |
Output is correct |
4 |
Correct |
108 ms |
9136 KB |
Output is correct |
5 |
Correct |
149 ms |
9056 KB |
Output is correct |
6 |
Correct |
142 ms |
9036 KB |
Output is correct |
7 |
Correct |
138 ms |
8012 KB |
Output is correct |
8 |
Correct |
42 ms |
7720 KB |
Output is correct |
9 |
Correct |
235 ms |
23172 KB |
Output is correct |
10 |
Correct |
291 ms |
22556 KB |
Output is correct |
11 |
Correct |
268 ms |
22568 KB |
Output is correct |
12 |
Correct |
266 ms |
20176 KB |
Output is correct |
13 |
Correct |
136 ms |
24868 KB |
Output is correct |
14 |
Correct |
105 ms |
17648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
106 ms |
13004 KB |
Output is correct |
2 |
Correct |
305 ms |
20764 KB |
Output is correct |
3 |
Correct |
206 ms |
22604 KB |
Output is correct |
4 |
Correct |
153 ms |
18972 KB |
Output is correct |
5 |
Correct |
213 ms |
18564 KB |
Output is correct |
6 |
Correct |
188 ms |
18508 KB |
Output is correct |
7 |
Correct |
200 ms |
17020 KB |
Output is correct |
8 |
Correct |
215 ms |
22764 KB |
Output is correct |
9 |
Correct |
238 ms |
23072 KB |
Output is correct |
10 |
Correct |
294 ms |
22740 KB |
Output is correct |
11 |
Correct |
288 ms |
22736 KB |
Output is correct |
12 |
Correct |
288 ms |
20768 KB |
Output is correct |
13 |
Correct |
323 ms |
27964 KB |
Output is correct |
14 |
Correct |
140 ms |
18040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
246 ms |
23352 KB |
Output is correct |
2 |
Correct |
308 ms |
20716 KB |
Output is correct |
3 |
Correct |
157 ms |
27656 KB |
Output is correct |
4 |
Correct |
251 ms |
23216 KB |
Output is correct |
5 |
Correct |
338 ms |
22752 KB |
Output is correct |
6 |
Correct |
295 ms |
22624 KB |
Output is correct |
7 |
Correct |
289 ms |
20700 KB |
Output is correct |
8 |
Correct |
155 ms |
27596 KB |
Output is correct |
9 |
Correct |
121 ms |
17652 KB |
Output is correct |