#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]]
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].back()]];
}
}
// 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::addBall()':
ballmachine.cpp:59:3: error: expected ';' before 'if'
if (par[vToRemove] != -1) {
^~
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);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
