#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)
|| (par[hldPaths[cPath].back()] != -1 and !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:75: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:100: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:103: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:114: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 |
4 ms |
504 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
115 ms |
29832 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
110 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
7 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
4 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
4 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Incorrect |
5 ms |
32188 KB |
Output isn't correct |
| 8 |
Runtime error |
5 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
11 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
30 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
130 ms |
32188 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
160 ms |
33724 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
154 ms |
33772 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
58 ms |
33772 KB |
Output is correct |
| 2 |
Runtime error |
191 ms |
50280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Runtime error |
183 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Runtime error |
70 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
63 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
58 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
50 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
58 ms |
52864 KB |
Output is correct |
| 9 |
Runtime error |
183 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
229 ms |
52864 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
215 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
202 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
225 ms |
52884 KB |
Output is correct |
| 14 |
Runtime error |
159 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
164 ms |
52884 KB |
Output isn't correct |
| 2 |
Runtime error |
331 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
217 ms |
52884 KB |
Output is correct |
| 4 |
Runtime error |
162 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
187 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
157 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
142 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
185 ms |
52884 KB |
Output is correct |
| 9 |
Runtime error |
333 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
326 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
386 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
344 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Correct |
285 ms |
52884 KB |
Output is correct |
| 14 |
Runtime error |
208 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
182 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Runtime error |
205 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Correct |
188 ms |
52884 KB |
Output is correct |
| 4 |
Runtime error |
189 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Runtime error |
192 ms |
52884 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
197 ms |
52896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
223 ms |
52896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Correct |
206 ms |
52896 KB |
Output is correct |
| 9 |
Runtime error |
161 ms |
52896 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
