/* 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], direct_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 >> direct_par[i];
direct_par[i]--;
if (direct_par[i] == -1)
continue;
adj[direct_par[i]].push_back(i);
adj[i].push_back(direct_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] = direct_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 | }
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1051 ms |
6744 KB |
Time limit exceeded |
2 |
Execution timed out |
1037 ms |
20048 KB |
Time limit exceeded |
3 |
Incorrect |
55 ms |
20304 KB |
Output isn't correct |
4 |
Execution timed out |
1072 ms |
6748 KB |
Time limit exceeded |
5 |
Execution timed out |
1076 ms |
6748 KB |
Time limit exceeded |
6 |
Incorrect |
1 ms |
6744 KB |
Output isn't correct |
7 |
Execution timed out |
1093 ms |
6748 KB |
Time limit exceeded |
8 |
Execution timed out |
1037 ms |
6744 KB |
Time limit exceeded |
9 |
Execution timed out |
1045 ms |
7004 KB |
Time limit exceeded |
10 |
Execution timed out |
1053 ms |
10076 KB |
Time limit exceeded |
11 |
Execution timed out |
1057 ms |
20060 KB |
Time limit exceeded |
12 |
Incorrect |
53 ms |
20308 KB |
Output isn't correct |
13 |
Execution timed out |
1039 ms |
20172 KB |
Time limit exceeded |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
29 ms |
12888 KB |
Output is correct |
2 |
Incorrect |
120 ms |
28140 KB |
Output isn't correct |
3 |
Incorrect |
70 ms |
23392 KB |
Output isn't correct |
4 |
Execution timed out |
1050 ms |
15684 KB |
Time limit exceeded |
5 |
Execution timed out |
1080 ms |
15192 KB |
Time limit exceeded |
6 |
Incorrect |
53 ms |
15860 KB |
Output isn't correct |
7 |
Execution timed out |
1094 ms |
14560 KB |
Time limit exceeded |
8 |
Correct |
27 ms |
12888 KB |
Output is correct |
9 |
Incorrect |
126 ms |
30844 KB |
Output isn't correct |
10 |
Incorrect |
151 ms |
28012 KB |
Output isn't correct |
11 |
Incorrect |
142 ms |
28556 KB |
Output isn't correct |
12 |
Execution timed out |
1059 ms |
28764 KB |
Time limit exceeded |
13 |
Correct |
76 ms |
32688 KB |
Output is correct |
14 |
Incorrect |
67 ms |
23212 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
66 ms |
19792 KB |
Output isn't correct |
2 |
Incorrect |
171 ms |
28244 KB |
Output isn't correct |
3 |
Incorrect |
108 ms |
30804 KB |
Output isn't correct |
4 |
Incorrect |
98 ms |
27712 KB |
Output isn't correct |
5 |
Incorrect |
84 ms |
25812 KB |
Output isn't correct |
6 |
Incorrect |
81 ms |
27152 KB |
Output isn't correct |
7 |
Incorrect |
93 ms |
25168 KB |
Output isn't correct |
8 |
Incorrect |
106 ms |
30808 KB |
Output isn't correct |
9 |
Incorrect |
169 ms |
30996 KB |
Output isn't correct |
10 |
Incorrect |
168 ms |
28024 KB |
Output isn't correct |
11 |
Incorrect |
151 ms |
30040 KB |
Output isn't correct |
12 |
Incorrect |
155 ms |
28392 KB |
Output isn't correct |
13 |
Incorrect |
161 ms |
36260 KB |
Output isn't correct |
14 |
Incorrect |
129 ms |
23088 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
179 ms |
31300 KB |
Output isn't correct |
2 |
Incorrect |
135 ms |
27284 KB |
Output isn't correct |
3 |
Correct |
139 ms |
34592 KB |
Output is correct |
4 |
Incorrect |
187 ms |
31192 KB |
Output isn't correct |
5 |
Incorrect |
193 ms |
27520 KB |
Output isn't correct |
6 |
Incorrect |
118 ms |
28852 KB |
Output isn't correct |
7 |
Incorrect |
151 ms |
27392 KB |
Output isn't correct |
8 |
Correct |
118 ms |
34408 KB |
Output is correct |
9 |
Incorrect |
86 ms |
23212 KB |
Output isn't correct |