#include <bits/stdc++.h>
using namespace std;
int n, q;
vector <int> e[100010];
int ti, pos[100010], ord[100010];
int minc[100010];
void dfs1(int u) {
minc[u] = n + 1;
for (auto v: e[u]) {
dfs1(v);
if (minc[v] < minc[u]) {
minc[u] = minc[v];
}
}
minc[u] = min(minc[u], u);
}
void dfs2(int u) {
ord[ti] = u;
pos[u] = ti--;
for (auto v: e[u]) dfs2(v);
}
int st[400010];
void update(int id, int l, int r, int i, int val) {
if (i > r || i < l) return;
if (l == r) {
st[id] = 1;
return;
}
int mid = l + r >> 1;
update(id * 2, l, mid, i, val);
update(id * 2 + 1, mid + 1, r, i, val);
st[id] = min(st[id * 2], st[id * 2 + 1]);
}
int get(int id, int l, int r) {
if (l == r) return l;
int mid = l + r >> 1;
if (st[id * 2] == 0) return get(id * 2, l, mid);
else return get(id * 2 + 1, mid + 1, r);
}
int cmp(int u, int v) {
return minc[u] > minc[v];
}
int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; ++i) {
int p;
scanf("%d", &p);
e[p].push_back(i);
}
ti = n;
dfs1(e[0].front());
for (int u = 1; u <= n; ++u)
sort(e[u].begin(), e[u].end(), cmp);
dfs2(e[0].front());
// for (int i = 1; i <= n; ++i) cout << ord[i] << " ";
while (q--) {
int c, k;
scanf("%d%d", &c, &k);
if (c == 1) {
int ans = 0;
while (k--) {
ans = get(1, 1, n);
update(1, 1, n, ans, 1);
}
cout << ord[ans] << "\n";
}
else {
update(1, 1, n, k, 0);
cout << "0\n";
}
}
}
Compilation message
ballmachine.cpp: In function 'void update(int, int, int, int, int)':
ballmachine.cpp:35:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | int mid = l + r >> 1;
| ~~^~~
ballmachine.cpp: In function 'int get(int, int, int)':
ballmachine.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = l + r >> 1;
| ~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:53:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
53 | scanf("%d%d", &n, &q);
| ~~~~~^~~~~~~~~~~~~~~~
ballmachine.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &p);
| ~~~~~^~~~~~~~~~
ballmachine.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
67 | scanf("%d%d", &c, &k);
| ~~~~~^~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
2 |
Incorrect |
75 ms |
6268 KB |
Output isn't correct |
3 |
Incorrect |
55 ms |
6200 KB |
Output isn't correct |
4 |
Incorrect |
2 ms |
2656 KB |
Output isn't correct |
5 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
6 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
7 |
Incorrect |
3 ms |
2644 KB |
Output isn't correct |
8 |
Incorrect |
2 ms |
2644 KB |
Output isn't correct |
9 |
Incorrect |
6 ms |
2804 KB |
Output isn't correct |
10 |
Incorrect |
18 ms |
3412 KB |
Output isn't correct |
11 |
Incorrect |
74 ms |
6184 KB |
Output isn't correct |
12 |
Incorrect |
56 ms |
6096 KB |
Output isn't correct |
13 |
Incorrect |
73 ms |
6184 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
36 ms |
5548 KB |
Output isn't correct |
2 |
Incorrect |
103 ms |
11348 KB |
Output isn't correct |
3 |
Incorrect |
66 ms |
7024 KB |
Output isn't correct |
4 |
Incorrect |
57 ms |
5708 KB |
Output isn't correct |
5 |
Incorrect |
54 ms |
5708 KB |
Output isn't correct |
6 |
Incorrect |
50 ms |
5696 KB |
Output isn't correct |
7 |
Incorrect |
51 ms |
5096 KB |
Output isn't correct |
8 |
Incorrect |
35 ms |
5580 KB |
Output isn't correct |
9 |
Incorrect |
96 ms |
11892 KB |
Output isn't correct |
10 |
Incorrect |
93 ms |
11348 KB |
Output isn't correct |
11 |
Incorrect |
94 ms |
11364 KB |
Output isn't correct |
12 |
Incorrect |
90 ms |
9676 KB |
Output isn't correct |
13 |
Incorrect |
72 ms |
13996 KB |
Output isn't correct |
14 |
Incorrect |
71 ms |
7048 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
44 ms |
7224 KB |
Output isn't correct |
2 |
Incorrect |
94 ms |
9792 KB |
Output isn't correct |
3 |
Incorrect |
62 ms |
13068 KB |
Output isn't correct |
4 |
Incorrect |
60 ms |
10036 KB |
Output isn't correct |
5 |
Incorrect |
61 ms |
9668 KB |
Output isn't correct |
6 |
Incorrect |
63 ms |
9720 KB |
Output isn't correct |
7 |
Incorrect |
59 ms |
8396 KB |
Output isn't correct |
8 |
Incorrect |
67 ms |
13076 KB |
Output isn't correct |
9 |
Incorrect |
92 ms |
11836 KB |
Output isn't correct |
10 |
Incorrect |
92 ms |
11452 KB |
Output isn't correct |
11 |
Incorrect |
90 ms |
11588 KB |
Output isn't correct |
12 |
Incorrect |
90 ms |
9800 KB |
Output isn't correct |
13 |
Incorrect |
98 ms |
15668 KB |
Output isn't correct |
14 |
Incorrect |
85 ms |
7752 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
99 ms |
11988 KB |
Output isn't correct |
2 |
Incorrect |
96 ms |
9888 KB |
Output isn't correct |
3 |
Incorrect |
78 ms |
15240 KB |
Output isn't correct |
4 |
Incorrect |
117 ms |
12000 KB |
Output isn't correct |
5 |
Incorrect |
91 ms |
11440 KB |
Output isn't correct |
6 |
Incorrect |
97 ms |
11452 KB |
Output isn't correct |
7 |
Incorrect |
91 ms |
9872 KB |
Output isn't correct |
8 |
Incorrect |
82 ms |
15316 KB |
Output isn't correct |
9 |
Incorrect |
68 ms |
7060 KB |
Output isn't correct |