#include <bits/stdc++.h>
using namespace std;
#define maxn 100010
#define pii pair<int, int>
int N, Q;
int par[18][maxn];
vector<int> ch[maxn];
vector<int> order;
int rt;
int minsub[maxn];
bool isin[maxn];
int myindo[maxn];
void getorder(int u) {
vector<pii> nch;
for (int v : ch[u]) {
nch.push_back(pii(minsub[v], v));
}
sort(nch.begin(), nch.end());
for (pii vp : nch) {
getorder(vp.second);
}
order.push_back(u);
}
void godown(int u) {
minsub[u] = u;
for (int v : ch[u]) {
godown(v);
minsub[u] = min(minsub[u], minsub[v]);
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> Q;
for (int i = 1; i <= N; i++) {
cin >> par[0][i];
ch[par[0][i]].push_back(i);
}
rt = ch[0][0];
godown(rt);
getorder(rt);
for (int i = 1; i < 18; i++) {
for (int j = 1; j <= N; j++) {
par[i][j] = par[i-1][par[i-1][j]];
}
}
int tp, x;
set<pii> open;
int ct = 0;
for (int v : order) {
open.insert(pii(ct++, v));
}
for (int i = 0; i < order.size(); i++) {
myindo[order[i]] = i;
}
while (Q--) {
cin >> tp >> x;
if (tp == 1) {
int ans = -1;
while (x--) {
pii cur = *(open.begin());
open.erase(open.begin());
isin[cur.second] = true;
ans = cur.second;
}
cout << ans << '\n';
}
else {
int tempo = x;
int numfall = 0;
for (int i = 17; i >= 0; i--) {
if (isin[par[i][tempo]]) {
numfall += (1 << i);
tempo = par[i][tempo];
}
}
cout << numfall << '\n';
isin[tempo] = false;
open.insert(pii(myindo[tempo], tempo));
}
}
cout.flush();
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < order.size(); i++) {
~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
2808 KB |
Output is correct |
2 |
Correct |
171 ms |
13708 KB |
Output is correct |
3 |
Correct |
84 ms |
14896 KB |
Output is correct |
4 |
Correct |
5 ms |
14896 KB |
Output is correct |
5 |
Correct |
5 ms |
14896 KB |
Output is correct |
6 |
Correct |
5 ms |
14896 KB |
Output is correct |
7 |
Correct |
5 ms |
14896 KB |
Output is correct |
8 |
Correct |
5 ms |
14896 KB |
Output is correct |
9 |
Correct |
12 ms |
14896 KB |
Output is correct |
10 |
Correct |
32 ms |
14896 KB |
Output is correct |
11 |
Correct |
171 ms |
16732 KB |
Output is correct |
12 |
Correct |
88 ms |
17512 KB |
Output is correct |
13 |
Correct |
125 ms |
18596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
45 ms |
18596 KB |
Output is correct |
2 |
Correct |
212 ms |
30684 KB |
Output is correct |
3 |
Correct |
110 ms |
30684 KB |
Output is correct |
4 |
Correct |
82 ms |
30684 KB |
Output is correct |
5 |
Correct |
80 ms |
30684 KB |
Output is correct |
6 |
Correct |
73 ms |
30684 KB |
Output is correct |
7 |
Correct |
79 ms |
30684 KB |
Output is correct |
8 |
Correct |
44 ms |
30684 KB |
Output is correct |
9 |
Correct |
212 ms |
37064 KB |
Output is correct |
10 |
Correct |
200 ms |
37932 KB |
Output is correct |
11 |
Correct |
169 ms |
39152 KB |
Output is correct |
12 |
Correct |
204 ms |
39152 KB |
Output is correct |
13 |
Correct |
142 ms |
44984 KB |
Output is correct |
14 |
Correct |
107 ms |
44984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
101 ms |
44984 KB |
Output is correct |
2 |
Correct |
282 ms |
44984 KB |
Output is correct |
3 |
Correct |
200 ms |
46612 KB |
Output is correct |
4 |
Correct |
170 ms |
46612 KB |
Output is correct |
5 |
Correct |
181 ms |
46612 KB |
Output is correct |
6 |
Correct |
203 ms |
46612 KB |
Output is correct |
7 |
Correct |
179 ms |
46612 KB |
Output is correct |
8 |
Correct |
173 ms |
51308 KB |
Output is correct |
9 |
Correct |
279 ms |
52228 KB |
Output is correct |
10 |
Correct |
271 ms |
53124 KB |
Output is correct |
11 |
Correct |
259 ms |
54480 KB |
Output is correct |
12 |
Correct |
258 ms |
54480 KB |
Output is correct |
13 |
Correct |
276 ms |
63224 KB |
Output is correct |
14 |
Correct |
239 ms |
63224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
249 ms |
63224 KB |
Output is correct |
2 |
Correct |
257 ms |
63224 KB |
Output is correct |
3 |
Correct |
171 ms |
68232 KB |
Output is correct |
4 |
Correct |
226 ms |
68232 KB |
Output is correct |
5 |
Correct |
241 ms |
68232 KB |
Output is correct |
6 |
Correct |
172 ms |
68232 KB |
Output is correct |
7 |
Correct |
233 ms |
68232 KB |
Output is correct |
8 |
Correct |
169 ms |
74736 KB |
Output is correct |
9 |
Correct |
115 ms |
74736 KB |
Output is correct |