#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g, b_jump;
vector<int> par, way, pos, sub;
vector<bool> ball;
int jump(int u, int h) {
if (u == -1) return 0;
if (h == 0) return u;
int x = 31 - __builtin_clz(h);
return jump(b_jump[u][x], h - (1 << x));
}
void dfs1(int u) {
sub[u] = u;
for (int h = 0; (1 << h) <= way.size(); h++) {
b_jump[u][h] = way[(int) way.size() - (1 << h)];
}
way.emplace_back(u);
for (int v: g[u]) {
dfs1(v);
sub[u] = min(sub[u], sub[v]);
}
way.pop_back();
}
void dfs2(int u) {
for (int v: g[u]) {
dfs2(v);
}
way.emplace_back(u);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr);
int n, q, h = 0;
cin >> n >> q;
while ((1 << h) < n) h++;
b_jump.assign(n + 1, vector<int>(h + 1, -1));
g.assign(n + 1, {});
par.assign(n + 1, 0);
ball.assign(n + 1, false);
sub.assign(n + 1, 0);
pos.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> par[i];
g[par[i]].emplace_back(i);
}
way.clear();
dfs1(0);
for (int i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end(), [&](int u, int v) {
return sub[u] < sub[v];
});
}
way.clear();
dfs2(0);
set<pair<int, int>> emp;
for (int i = 0; i < n; i++) {
emp.insert({i, way[i]});
pos[way[i]] = i;
}
while (q--) {
int t, x;
cin >> t >> x;
if (t == 1) {
int i = 0, last = 0;
vector<pair<int, int>> del;
for (auto it = emp.begin(); i < x; i++, it++) {
last = (*it).second;
ball[(*it).second] = true;
del.push_back(*it);
}
for (auto it: del) {
emp.erase(it);
}
cout << last << '\n';
} else {
int l = 0, r = n - 1, best = -1;
while (l <= r) {
int m = (l + r) >> 1;
int u = jump(x, m);
if (ball[u] and !ball[par[u]]) {
best = m;
break;
}
if (ball[par[u]]) {
l = m + 1;
} else {
r = m - 1;
}
}
assert(best >= 0);
x = jump(x, best);
ball[x] = false;
emp.insert({pos[x], x});
cout << best << '\n';
}
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void dfs1(int)':
ballmachine.cpp:19:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
19 | for (int h = 0; (1 << h) <= way.size(); h++) {
| ~~~~~~~~~^~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
161 ms |
14552 KB |
Output is correct |
3 |
Correct |
70 ms |
13984 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
7 ms |
1108 KB |
Output is correct |
10 |
Correct |
29 ms |
3812 KB |
Output is correct |
11 |
Correct |
164 ms |
14552 KB |
Output is correct |
12 |
Correct |
72 ms |
14044 KB |
Output is correct |
13 |
Correct |
115 ms |
13896 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
51 ms |
5644 KB |
Output is correct |
2 |
Correct |
535 ms |
25300 KB |
Output is correct |
3 |
Correct |
88 ms |
20620 KB |
Output is correct |
4 |
Correct |
129 ms |
8112 KB |
Output is correct |
5 |
Correct |
184 ms |
7936 KB |
Output is correct |
6 |
Correct |
170 ms |
7684 KB |
Output is correct |
7 |
Correct |
158 ms |
6868 KB |
Output is correct |
8 |
Correct |
52 ms |
5836 KB |
Output is correct |
9 |
Correct |
378 ms |
25560 KB |
Output is correct |
10 |
Correct |
595 ms |
25320 KB |
Output is correct |
11 |
Correct |
344 ms |
24576 KB |
Output is correct |
12 |
Correct |
442 ms |
23240 KB |
Output is correct |
13 |
Correct |
147 ms |
25536 KB |
Output is correct |
14 |
Correct |
91 ms |
20548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
128 ms |
13004 KB |
Output is correct |
2 |
Correct |
645 ms |
23792 KB |
Output is correct |
3 |
Correct |
267 ms |
23588 KB |
Output is correct |
4 |
Correct |
255 ms |
20488 KB |
Output is correct |
5 |
Correct |
400 ms |
20172 KB |
Output is correct |
6 |
Correct |
328 ms |
20104 KB |
Output is correct |
7 |
Correct |
385 ms |
18916 KB |
Output is correct |
8 |
Correct |
317 ms |
23628 KB |
Output is correct |
9 |
Correct |
345 ms |
25740 KB |
Output is correct |
10 |
Correct |
586 ms |
25336 KB |
Output is correct |
11 |
Correct |
540 ms |
25252 KB |
Output is correct |
12 |
Correct |
537 ms |
23700 KB |
Output is correct |
13 |
Correct |
685 ms |
29648 KB |
Output is correct |
14 |
Correct |
157 ms |
21548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
475 ms |
25940 KB |
Output is correct |
2 |
Correct |
602 ms |
23744 KB |
Output is correct |
3 |
Correct |
179 ms |
28956 KB |
Output is correct |
4 |
Correct |
431 ms |
25892 KB |
Output is correct |
5 |
Correct |
684 ms |
25308 KB |
Output is correct |
6 |
Correct |
384 ms |
24576 KB |
Output is correct |
7 |
Correct |
460 ms |
23788 KB |
Output is correct |
8 |
Correct |
175 ms |
28800 KB |
Output is correct |
9 |
Correct |
92 ms |
20644 KB |
Output is correct |