#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;
struct BallMachine {
vector<vector<int>> tree, hldPaths;
vector<int> par, pathIn, placeInPath, highestFilled, st, childCount, depth;
vector<bool> filled;
set<pair<int, int>> leafSet;
int travT = 0, root;
int findInfo(int v, int p, int level) {
st[v] = travT++;
par[v] = p;
depth[v] = level;
int stSize = 1;
int bestChild = -1, bchilds = -1;
for (int child : tree[v]) {
// printf("%d att %d\n", v, child);
if (child != p) {
int childSize = findInfo(child, v, level + 1);
if (childSize > bchilds) {
bestChild = child, bchilds = childSize;
}
stSize += childSize;
++childCount[v];
}
}
int pathToAdd = -1;
// printf("%d in path %d\n", v, pathToAdd);
if (stSize == 1) {
hldPaths.emplace_back(1, -1);
pathToAdd = hldPaths.size();
leafSet.emplace(st[v], v);
highestFilled.push_back(0);
// printf("%d leaf\n", v);
} else {
pathToAdd = pathIn[bestChild];
}
placeInPath[v] = hldPaths[pathToAdd].size();
hldPaths[pathToAdd].push_back(v);
pathIn[v] = pathToAdd;
// printf("searching %d\n", v + 1);
// printf("%d in path %d\n", v + 1, pathToAdd);
return stSize;
}
BallMachine(vector<vector<int>> tree, int rt) : tree(tree),
par(tree.size()), pathIn(tree.size()), placeInPath(tree.size()), st(tree.size()),
childCount(tree.size()), depth(tree.size()), filled(tree.size()), root(rt)
{findInfo(root, -1, 0);}
int addBall() { // returns place where ball was placed
int vToRemove = leafSet.begin()->second;
// printf("making %d filled\n", vToRemove);
leafSet.erase(make_pair(st[vToRemove], vToRemove));
highestFilled[pathIn[vToRemove]] = placeInPath[vToRemove];
if (par[vToRemove] != -1) {
--childCount[par[vToRemove]];
if (childCount[par[vToRemove]] == 0) {
leafSet.emplace(st[par[vToRemove]], par[vToRemove]);
}
}
filled[vToRemove] = true;
return vToRemove;
}
int deleteBall(int x) { // returns number of shifted balls
int vToBlank = -1;
// printf("deleting %d\n", x + 1);
for (int cPath = pathIn[x];;) {
// printf("in path %d root %d\n", cPath, root);
// printf("highfill in path is %d\n", hldPaths[cPath][highestFilled[cPath]]);
if ((hldPaths[cPath][highestFilled[cPath]] == root)
|| (highestFilled[cPath] != hldPaths[cPath].size() - 1)
|| (!filled[par[hldPaths[cPath].back()]])) {
// we can stop at this vertex
// printf("case goes here\n");
vToBlank = hldPaths[cPath][highestFilled[cPath]]; break;
} else {
// we need to climb further
cPath = pathIn[par[hldPaths[cPath][highestFilled[cPath]]]];
}
}
// printf("found vtb: %d\n", vToBlank + 1);
filled[vToBlank] = false;
if (par[vToBlank] != -1) {
++childCount[par[vToBlank]];
if (childCount[par[vToBlank]] == 1) {
leafSet.erase(make_pair(st[par[vToBlank]], par[vToBlank]));
}
}
leafSet.insert(make_pair(st[vToBlank], vToBlank));
--highestFilled[pathIn[vToBlank]];
return depth[x] - depth[vToBlank];
}
};
int main() {
int n, q, root = 0; scanf("%d %d", &n, &q);
vector<vector<int>> tree(n);
for (int i = 0; i < n; ++i) {
int par; scanf("%d", &par);
--par;
if (par >= 0) {
tree[par].push_back(i);
tree[i].push_back(par);
} else {
root = i;
}
}
BallMachine bm(tree, root);
for (int qta = 0; qta < q; ++qta) {
int type, param; scanf("%d %d", &type, ¶m);
if (type == 1) {
int ans = -1;
for (int rep = 1; rep <= param; ++rep) ans = bm.addBall();
printf("%d\n", ans + 1);
} else {
printf("%d\n", bm.deleteBall(--param));
}
}
return 0;
}
Compilation message
ballmachine.cpp: In member function 'int BallMachine::deleteBall(int)':
ballmachine.cpp:74:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
|| (highestFilled[cPath] != hldPaths[cPath].size() - 1)
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:99:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q, root = 0; scanf("%d %d", &n, &q);
~~~~~^~~~~~~~~~~~~~~~~
ballmachine.cpp:102:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int par; scanf("%d", &par);
~~~~~^~~~~~~~~~~~
ballmachine.cpp:113:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int type, param; scanf("%d %d", &type, ¶m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
3 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
55 ms |
25208 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
62 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
4 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
4 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
3 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
4 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
3 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
8 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
22 ms |
25240 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
69 ms |
25552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
81 ms |
25552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
51 ms |
25552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
26 ms |
25552 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
83 ms |
38472 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
98 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
32 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
29 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
29 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
24 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
20 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
101 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
106 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
111 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
103 ms |
39508 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
125 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
89 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
50 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
119 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
109 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
92 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
76 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
69 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
69 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
106 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
86 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
125 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
109 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
105 ms |
43844 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
125 ms |
49488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
88 ms |
49488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
49488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
116 ms |
49488 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
143 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
103 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
95 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
102 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
92 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
172 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
87 ms |
49628 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
