#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) {
pathToAdd = hldPaths.size();
hldPaths.emplace_back(1, -1);
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 |
2 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
120 ms |
29268 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
101 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
5 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
4 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
3 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
4 ms |
30876 KB |
Output isn't correct |
| 8 |
Runtime error |
4 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
8 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
30 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
101 ms |
30876 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
122 ms |
31068 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
99 ms |
31084 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
46 ms |
31084 KB |
Output is correct |
| 2 |
Runtime error |
192 ms |
47624 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
175 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
55 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
38 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
39 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
36 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
45 ms |
50344 KB |
Output is correct |
| 9 |
Runtime error |
155 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
155 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
199 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
152 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
149 ms |
50344 KB |
Output is correct |
| 14 |
Runtime error |
154 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
50344 KB |
Output isn't correct |
| 2 |
Runtime error |
339 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
181 ms |
50344 KB |
Output is correct |
| 4 |
Runtime error |
178 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
168 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
178 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
162 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
143 ms |
50344 KB |
Output is correct |
| 9 |
Runtime error |
262 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
341 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
358 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
319 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
192 ms |
50344 KB |
Output is correct |
| 14 |
Runtime error |
178 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
153 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
196 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
170 ms |
50344 KB |
Output is correct |
| 4 |
Runtime error |
160 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
157 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
224 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
179 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
209 ms |
50344 KB |
Output is correct |
| 9 |
Runtime error |
169 ms |
50344 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
