#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
int findMinSubtree(int node, vector<int> children[], int minSubtree[])
{
if (minSubtree[node] > 0)
return minSubtree[node];
int temp = node;
for (int child : children[node])
temp = min(temp, findMinSubtree(child, children, minSubtree));
minSubtree[node] = temp;
return temp;
}
void visitOrdered(int node, vector<int> children[], vector<int> &order)
{
for (int child : children[node])
visitOrdered(child, children, order);
order.push_back(node);
}
void findUp(int node, vector<int> children[], int parent[], vector<vector<int>> &up, int logN, int depth[])
{
up[node][0] = parent[node] == 0 ? node : parent[node];
for (int i = 1; i <= logN; i++)
up[node][i] = up[up[node][i - 1]][i - 1];
for (int child : children[node])
{
depth[child] = depth[node] + 1;
findUp(child, children, parent, up, logN, depth);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, q;
cin >> n >> q;
int parent[n + 5];
int minSubtree[n + 5];
bool hasBall[n + 5];
vector<int> children[n + 5];
int root;
for (int i = 1; i <= n; i++)
{
hasBall[i] = false;
minSubtree[i] = 0;
cin >> parent[i];
if (parent[i] == 0)
root = i;
else
children[parent[i]].push_back(i);
}
findMinSubtree(root, children, minSubtree);
for (int i = 1; i <= n; i++)
{
sort(children[i].begin(), children[i].end(), [&minSubtree](const int node1, const int node2)
{ return minSubtree[node1] < minSubtree[node2]; });
}
int logN = (int)ceil(log2(n));
int depth[n + 5];
depth[root] = 0;
vector<vector<int>> up(n + 5, vector<int>(logN + 1));
findUp(root, children, parent, up, logN, depth);
vector<int> orderToNode, nodeToOrder(n + 5);
visitOrdered(root, children, orderToNode);
for (int i = 0; i < orderToNode.size(); i++)
nodeToOrder[orderToNode[i]] = i;
int r = 0;
priority_queue<int, vector<int>, greater<int>> orderToFill;
for (int i = 0; i < q; i++)
{
int t, k;
cin >> t >> k;
if (t == 1)
{
int lastFilled = -1;
while (k > 0 && !orderToFill.empty())
{
hasBall[orderToNode[orderToFill.top()]] = true;
lastFilled = orderToNode[orderToFill.top()];
orderToFill.pop();
k--;
}
if (k == 0)
{
cout << lastFilled << endl;
}
else
{
for (int j = 0; j < k; j++)
hasBall[orderToNode[r + j]] = true;
r += k;
cout << orderToNode[r - 1] << endl;
}
}
else
{
int temp = logN;
int tempNode = k;
int target = k;
while (temp >= 0 && target != root)
{
if (hasBall[up[tempNode][temp]])
{
target = up[tempNode][temp];
tempNode = up[tempNode][temp];
}
temp--;
}
hasBall[target] = false;
orderToFill.push(nodeToOrder[target]);
cout << (depth[k] - depth[target]) << endl;
}
}
}
Compilation message
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for (int i = 0; i < orderToNode.size(); i++)
| ~~^~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:117:40: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
117 | while (temp >= 0 && target != root)
| ~~~~~~~^~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
332 KB |
Output is correct |
2 |
Correct |
192 ms |
11280 KB |
Output is correct |
3 |
Correct |
163 ms |
11408 KB |
Output is correct |
4 |
Correct |
1 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
2 ms |
460 KB |
Output is correct |
7 |
Correct |
2 ms |
460 KB |
Output is correct |
8 |
Correct |
3 ms |
460 KB |
Output is correct |
9 |
Correct |
15 ms |
972 KB |
Output is correct |
10 |
Correct |
46 ms |
3020 KB |
Output is correct |
11 |
Correct |
183 ms |
11428 KB |
Output is correct |
12 |
Correct |
173 ms |
11348 KB |
Output is correct |
13 |
Correct |
181 ms |
11332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
118 ms |
5268 KB |
Output is correct |
2 |
Correct |
261 ms |
21492 KB |
Output is correct |
3 |
Correct |
190 ms |
16572 KB |
Output is correct |
4 |
Correct |
134 ms |
6932 KB |
Output is correct |
5 |
Correct |
157 ms |
6768 KB |
Output is correct |
6 |
Correct |
129 ms |
6632 KB |
Output is correct |
7 |
Correct |
132 ms |
5676 KB |
Output is correct |
8 |
Correct |
113 ms |
5364 KB |
Output is correct |
9 |
Correct |
240 ms |
21744 KB |
Output is correct |
10 |
Correct |
251 ms |
21376 KB |
Output is correct |
11 |
Correct |
228 ms |
21020 KB |
Output is correct |
12 |
Correct |
251 ms |
19000 KB |
Output is correct |
13 |
Correct |
227 ms |
23364 KB |
Output is correct |
14 |
Correct |
174 ms |
16544 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
132 ms |
11220 KB |
Output is correct |
2 |
Correct |
285 ms |
19900 KB |
Output is correct |
3 |
Correct |
186 ms |
21532 KB |
Output is correct |
4 |
Correct |
159 ms |
17656 KB |
Output is correct |
5 |
Correct |
165 ms |
17380 KB |
Output is correct |
6 |
Correct |
172 ms |
17272 KB |
Output is correct |
7 |
Correct |
206 ms |
15728 KB |
Output is correct |
8 |
Correct |
191 ms |
21564 KB |
Output is correct |
9 |
Correct |
244 ms |
22080 KB |
Output is correct |
10 |
Correct |
269 ms |
21764 KB |
Output is correct |
11 |
Correct |
268 ms |
21736 KB |
Output is correct |
12 |
Correct |
282 ms |
19812 KB |
Output is correct |
13 |
Correct |
289 ms |
26944 KB |
Output is correct |
14 |
Correct |
199 ms |
17212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
286 ms |
22204 KB |
Output is correct |
2 |
Correct |
273 ms |
19904 KB |
Output is correct |
3 |
Correct |
230 ms |
26336 KB |
Output is correct |
4 |
Correct |
287 ms |
22088 KB |
Output is correct |
5 |
Correct |
285 ms |
21508 KB |
Output is correct |
6 |
Correct |
251 ms |
21120 KB |
Output is correct |
7 |
Correct |
279 ms |
19804 KB |
Output is correct |
8 |
Correct |
224 ms |
26336 KB |
Output is correct |
9 |
Correct |
190 ms |
16636 KB |
Output is correct |