/* IN THE NAME OF GOD */
// Oh, let the bullets fly, oh, let them rain
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100'000, lg = 18;
bool is_filled[MAXN + 10];
int par_sp[MAXN + 10][lg + 10], order[MAXN + 10], mn[MAXN + 10], par[MAXN + 10], n, q, tt;
vector<int> adj[MAXN + 10];
set<pair<int, int>> take_order;
void input();
void solve();
void dfs_get_minimum(int u, int par);
void dfs_get_order(int u, int par);
void par_spars_table();
int query1(int cnt);
int query2(int id);
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
input();
solve();
return 0;
}
void input() {
cin >> n >> q;
for (int i = 0; i < n; i++) {
cin >> par[i];
par[i]--;
if (par[i] == -1)
continue;
adj[par[i]].push_back(i);
adj[i].push_back(par[i]);
}
}
void solve() {
dfs_get_minimum(0, -1);
dfs_get_order(0, -1);
par_spars_table();
//cout << par_sp[7][2] << '\n';
for (int i = 0; i < n; i++)
take_order.insert({order[i], i});
while (q--) {
int type, x;
cin >> type >> x;
if (type == 1)
cout << query1(x) + 1 << '\n';
else {
x--;
cout << query2(x) << '\n';
}
}
}
void dfs_get_minimum(int u, int par) {
int res = u;
for (int v : adj[u])
if (v != par) {
dfs_get_minimum(v, u);
res = min(res, mn[v]);
}
mn[u] = res;
}
void dfs_get_order(int u, int par) {
set<pair<int, int>> st;
for (int v : adj[u])
if (v != par)
st.insert({mn[v], v});
for (auto p : st)
dfs_get_order(p.second, u);
order[u] = tt++;
}
void par_spars_table() {
for (int i = 0; i < n; i++)
par_sp[i][0] = par[i];
for (int k = 1; k < lg; k++)
for (int i = 0; i < n; i++) {
if (par_sp[i][k - 1] == -1)
par_sp[i][k] = -1;
else
par_sp[i][k] = par_sp[par_sp[i][k - 1]][k - 1];
}
}
int query1(int cnt) {
for (int i = 0; i < cnt; i++) {
int u = (*take_order.begin()).second;
is_filled[u] = true;
take_order.erase(take_order.begin());
if (i == cnt - 1)
return u;
}
}
int query2(int id) {
int u = id, ans = 0;
for (int k = lg - 1; k >= 0; k--) {
if (par_sp[u][k] == -1)
continue;
if (is_filled[par_sp[u][k]] == true) {
u = par_sp[u][k];
ans += (1 << k);
}
}
is_filled[u] = false;
take_order.insert({order[u], u});
return ans;
}
Compilation message
ballmachine.cpp: In function 'int query1(int)':
ballmachine.cpp:100:1: warning: control reaches end of non-void function [-Wreturn-type]
100 | }
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1058 ms |
6748 KB |
Time limit exceeded |
| 2 |
Execution timed out |
1055 ms |
20764 KB |
Time limit exceeded |
| 3 |
Incorrect |
52 ms |
20304 KB |
Output isn't correct |
| 4 |
Execution timed out |
1026 ms |
6744 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1074 ms |
6744 KB |
Time limit exceeded |
| 6 |
Incorrect |
2 ms |
6748 KB |
Output isn't correct |
| 7 |
Execution timed out |
1092 ms |
6868 KB |
Time limit exceeded |
| 8 |
Execution timed out |
1010 ms |
6744 KB |
Time limit exceeded |
| 9 |
Execution timed out |
1046 ms |
7000 KB |
Time limit exceeded |
| 10 |
Execution timed out |
1066 ms |
10076 KB |
Time limit exceeded |
| 11 |
Execution timed out |
1068 ms |
20308 KB |
Time limit exceeded |
| 12 |
Incorrect |
56 ms |
20324 KB |
Output isn't correct |
| 13 |
Execution timed out |
1025 ms |
20560 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
13056 KB |
Output is correct |
| 2 |
Incorrect |
115 ms |
29396 KB |
Output isn't correct |
| 3 |
Incorrect |
67 ms |
23212 KB |
Output isn't correct |
| 4 |
Execution timed out |
1020 ms |
16216 KB |
Time limit exceeded |
| 5 |
Execution timed out |
1057 ms |
15444 KB |
Time limit exceeded |
| 6 |
Incorrect |
48 ms |
15820 KB |
Output isn't correct |
| 7 |
Execution timed out |
1081 ms |
14476 KB |
Time limit exceeded |
| 8 |
Correct |
26 ms |
12984 KB |
Output is correct |
| 9 |
Incorrect |
106 ms |
32084 KB |
Output isn't correct |
| 10 |
Incorrect |
116 ms |
29524 KB |
Output isn't correct |
| 11 |
Incorrect |
105 ms |
29008 KB |
Output isn't correct |
| 12 |
Execution timed out |
1060 ms |
30292 KB |
Time limit exceeded |
| 13 |
Correct |
79 ms |
32600 KB |
Output is correct |
| 14 |
Incorrect |
70 ms |
23244 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
54 ms |
20564 KB |
Output isn't correct |
| 2 |
Incorrect |
123 ms |
29516 KB |
Output isn't correct |
| 3 |
Incorrect |
91 ms |
31684 KB |
Output isn't correct |
| 4 |
Incorrect |
83 ms |
28500 KB |
Output isn't correct |
| 5 |
Incorrect |
82 ms |
26708 KB |
Output isn't correct |
| 6 |
Incorrect |
84 ms |
28188 KB |
Output isn't correct |
| 7 |
Incorrect |
78 ms |
26180 KB |
Output isn't correct |
| 8 |
Incorrect |
87 ms |
31568 KB |
Output isn't correct |
| 9 |
Incorrect |
124 ms |
32284 KB |
Output isn't correct |
| 10 |
Incorrect |
124 ms |
29268 KB |
Output isn't correct |
| 11 |
Incorrect |
127 ms |
31064 KB |
Output isn't correct |
| 12 |
Incorrect |
119 ms |
29516 KB |
Output isn't correct |
| 13 |
Incorrect |
151 ms |
37464 KB |
Output isn't correct |
| 14 |
Incorrect |
103 ms |
23240 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
32340 KB |
Output isn't correct |
| 2 |
Incorrect |
113 ms |
28552 KB |
Output isn't correct |
| 3 |
Correct |
86 ms |
34388 KB |
Output is correct |
| 4 |
Incorrect |
117 ms |
32504 KB |
Output isn't correct |
| 5 |
Incorrect |
113 ms |
28972 KB |
Output isn't correct |
| 6 |
Incorrect |
101 ms |
29136 KB |
Output isn't correct |
| 7 |
Incorrect |
116 ms |
28548 KB |
Output isn't correct |
| 8 |
Correct |
86 ms |
34384 KB |
Output is correct |
| 9 |
Incorrect |
67 ms |
23500 KB |
Output isn't correct |
