#include <bits/stdc++.h>
#define INF 999999999
#define MAXN 100100
using namespace std;
vector<vector<int> > treeAdj;
int smallestInSubtree[MAXN], depth[MAXN], reverseTree[MAXN], fillOrderId[MAXN], fillIdToNode[MAXN];
vector<vector<int> > jumpTable;
vector<bool> available;
priority_queue<int, vector<int>, greater<int> > availableSpots;
int n, q;
int root;
int lastRolledDepth;
void computeData(int node, int d){
int chld = treeAdj[node].size();
depth[node] = d;
//printf("Getting data for node %d (depth %d)\n", node, d);
if(chld == 0){
//printf("IT S A LEAF!\n");
smallestInSubtree[node] = node;
return;
}
int sml = node;
int v;
vector<pair<int, int> > newSortedAdj;
for(int i = 0; i < chld; i++){
v = treeAdj[node][i];
//printf("%d -th child of %d is %d\n", i+1, node, v);
computeData(v, d+1);
newSortedAdj.push_back({smallestInSubtree[v], v});
sml = min(sml, smallestInSubtree[v]);
}
sort(newSortedAdj.begin(), newSortedAdj.end());
for(int i = 0; i < chld; i++){
treeAdj[node][i] = newSortedAdj[i].second;
}
smallestInSubtree[node] = sml;
//printf("Got data for node %d (depth %d)\n", node, d);
return;
}
int computeFillOrderId(int node, int id){
int sz = treeAdj[node].size();
int v;
for(int i = 0; i < sz; i++){
v = treeAdj[node][i];
id = computeFillOrderId(v, id);
}
fillOrderId[node] = id;
fillIdToNode[id] = node;
//printf("Node %d has fill order id %d\n", node, id);
return id+1;
}
void computeJumpTable(int node){
int mxj;
if(node == root) mxj = 0;
else mxj = log2(depth[node])+1;
//printf("Can jump at most of %d from %d\n", mxj, node);
for(int i = 0; i < mxj; i++){
if(i == 0){
jumpTable[node][0] = reverseTree[node];
}
else{
jumpTable[node][i] = jumpTable[jumpTable[node][i-1]][i-1];
}
//printf("A jump of %d from %d lands at %d\n", 1<<i, node, jumpTable[node][i]);
}
int sz = treeAdj[node].size();
for(int i = 0; i < sz; i++){
computeJumpTable(treeAdj[node][i]);
}
}
int jumpInTree(int node, int jumpVal){
for(int i = 0; jumpVal != 0; jumpVal = jumpVal>>1){
//printf("Round %d, jumpVal is %d\n", i, jumpVal);
if(jumpVal&1){
// printf("Jumping of %d from %d\n", 1<<i, node);
node = jumpTable[node][i];
}
i++;
}
return node;
}
void printTreeState(){
printf("myIds: ");
for(int i = 0; i < n; i++){
printf("%d ", i);
}
printf("\nDepth: ");
for(int i = 0; i < n; i++){
printf("%d ", depth[i]);
}
printf("\nfree?: ");
for(int i = 0; i < n; i++){
printf("%d ", (available[i]?1:0));
}
printf("\n");
}
void addBallsWithPQ(int val){
int spot;
for(int i = 0; i < val; i++){
spot = availableSpots.top();
availableSpots.pop();
available[fillIdToNode[spot]] = false;
}
cout << fillIdToNode[spot]+1 << endl;
}
void removeBallWithPQ(int node){
if(!available[root]){
lastRolledDepth = depth[root];
available[root] = true;
availableSpots.push(root);
return;
}
int maxJump = depth[node];
int p;
for(int i = 0;; i++){
if((1LL << i) > maxJump){
p = i-1;
//printf("Stopped at i = %d cause would jump %d\n", i, (1<<i));
break;
}
}
//printf("Can jump at most %d\n", p);
for(int i = p; i >= 0; i--){
// printf("Checking %d as potential jump land from %d\n", jumpTable[node][i]);
if(!available[jumpTable[node][i]]){
node = jumpTable[node][i];
}
}
//printf("Found higher best stop to be %d\n",node);
lastRolledDepth = depth[node];
available[node] = true;
availableSpots.push(node);
return;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
int p;
cin >> n >> q;
treeAdj.resize(n);
jumpTable.resize(n);
available.assign(n, true);
int maxBinaryJump = log2(n)+1;
for(int i = 0; i < n; i++){
jumpTable[i].resize(maxBinaryJump);
cin >> p;
if(p == 0) root = i;
else{
treeAdj[p-1].push_back(i);
reverseTree[i] = p-1;
}
}
computeData(root, 0);
computeFillOrderId(root, 0);
computeJumpTable(root);
for(int i = 0; i < n; i++){
availableSpots.push(i);
}
int action, val;
for(int i = 0; i < q; i++){
cin >> action >> val;
if(action == 1){
addBallsWithPQ(val);
}
else{
val--;
removeBallWithPQ(val);
//cout << "Last rolled depth is " << *lastRolledDepth << endl;
cout << depth[val] - lastRolledDepth << endl;
}
//printTreeState();
}
return 0;
}
Compilation message
ballmachine.cpp: In function 'void addBallsWithPQ(int)':
ballmachine.cpp:125:9: warning: 'spot' may be used uninitialized in this function [-Wmaybe-uninitialized]
int spot;
^~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
2 |
Incorrect |
287 ms |
11636 KB |
Output isn't correct |
3 |
Incorrect |
256 ms |
11636 KB |
Output isn't correct |
4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
5 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
6 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
7 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
8 |
Incorrect |
5 ms |
512 KB |
Output isn't correct |
9 |
Incorrect |
18 ms |
1024 KB |
Output isn't correct |
10 |
Incorrect |
46 ms |
2936 KB |
Output isn't correct |
11 |
Incorrect |
298 ms |
11456 KB |
Output isn't correct |
12 |
Incorrect |
250 ms |
11816 KB |
Output isn't correct |
13 |
Incorrect |
302 ms |
11544 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
182 ms |
6412 KB |
Output isn't correct |
2 |
Incorrect |
487 ms |
23988 KB |
Output isn't correct |
3 |
Correct |
242 ms |
17388 KB |
Output is correct |
4 |
Incorrect |
192 ms |
7672 KB |
Output isn't correct |
5 |
Incorrect |
196 ms |
7668 KB |
Output isn't correct |
6 |
Incorrect |
235 ms |
7668 KB |
Output isn't correct |
7 |
Incorrect |
206 ms |
6280 KB |
Output isn't correct |
8 |
Incorrect |
196 ms |
6364 KB |
Output isn't correct |
9 |
Incorrect |
436 ms |
24308 KB |
Output isn't correct |
10 |
Incorrect |
452 ms |
23832 KB |
Output isn't correct |
11 |
Incorrect |
482 ms |
24064 KB |
Output isn't correct |
12 |
Incorrect |
451 ms |
20500 KB |
Output isn't correct |
13 |
Incorrect |
376 ms |
28020 KB |
Output isn't correct |
14 |
Correct |
281 ms |
17296 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
213 ms |
12484 KB |
Output isn't correct |
2 |
Incorrect |
568 ms |
20872 KB |
Output isn't correct |
3 |
Correct |
401 ms |
25316 KB |
Output is correct |
4 |
Incorrect |
315 ms |
19576 KB |
Output isn't correct |
5 |
Correct |
318 ms |
19344 KB |
Output is correct |
6 |
Correct |
334 ms |
19220 KB |
Output is correct |
7 |
Incorrect |
309 ms |
16828 KB |
Output isn't correct |
8 |
Correct |
330 ms |
25328 KB |
Output is correct |
9 |
Incorrect |
428 ms |
24564 KB |
Output isn't correct |
10 |
Incorrect |
444 ms |
24108 KB |
Output isn't correct |
11 |
Incorrect |
522 ms |
23988 KB |
Output isn't correct |
12 |
Incorrect |
483 ms |
20884 KB |
Output isn't correct |
13 |
Incorrect |
605 ms |
31632 KB |
Output isn't correct |
14 |
Incorrect |
317 ms |
17384 KB |
Output isn't correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
540 ms |
24528 KB |
Output isn't correct |
2 |
Incorrect |
517 ms |
20880 KB |
Output isn't correct |
3 |
Incorrect |
437 ms |
31472 KB |
Output isn't correct |
4 |
Incorrect |
541 ms |
24520 KB |
Output isn't correct |
5 |
Incorrect |
488 ms |
24012 KB |
Output isn't correct |
6 |
Incorrect |
414 ms |
23940 KB |
Output isn't correct |
7 |
Incorrect |
477 ms |
20812 KB |
Output isn't correct |
8 |
Incorrect |
394 ms |
31472 KB |
Output isn't correct |
9 |
Correct |
256 ms |
17452 KB |
Output is correct |