# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
72957 | 2018-08-27T09:51:27 Z | spacewalker | Ball Machine (BOI13_ballmachine) | C++14 | 1000 ms | 73280 KB |
#include <cstdio> #include <vector> #include <algorithm> #include <utility> #include <set> using namespace std; struct BallMachine { vector<vector<int>> tree, hldPaths; vector<int> highestFilled, par, pathIn, placeInPath, depth, st, blankChildCount; vector<bool> filled; set<pair<int, int>> leafSet; int root, t = 0; int getInfo(int i, int p, int level) { par[i] = p; depth[i] = level + 1; st[i] = t++; int stSize = 1, childCount = 0; int bestChild = -1, bcSize = -1; // printf("yeet %d\n", i); for (int c : tree[i]) { if (c != p) { ++childCount; int subtreeSize = getInfo(c, i, level + 1); if (subtreeSize > bcSize) { bestChild = c; bcSize = subtreeSize; } } } if (bestChild == -1) { pathIn[i] = hldPaths.size(); hldPaths.emplace_back(1, -1); hldPaths.back().push_back(i); highestFilled.push_back(0); placeInPath[i] = 1; leafSet.emplace(st[i], i); } else { pathIn[i] = pathIn[bestChild]; placeInPath[i] = hldPaths[pathIn[i]].size(); hldPaths[pathIn[i]].push_back(i); } blankChildCount[i] = childCount; return stSize; } BallMachine(vector<vector<int>> &tree, int &root) : tree(tree), par(tree.size()), pathIn(tree.size()), placeInPath(tree.size()), depth(tree.size()), st(tree.size()), blankChildCount(tree.size()), root(root), filled(tree.size(), false) { getInfo(root, -1, 0); } int addBall() { // returns where ball was added auto toFillPair = *leafSet.begin(); leafSet.erase(toFillPair); int vToFill = toFillPair.second; // update the HLD ++highestFilled[pathIn[vToFill]]; // update blankChildCount if (vToFill != root) { --blankChildCount[par[vToFill]]; // update leafset if (blankChildCount[par[vToFill]] == 0) { leafSet.emplace(st[par[vToFill]], par[vToFill]); } } filled[vToFill] = true; return vToFill; } int deleteBall(int x) { // returns # of shifted balls int vToBlank = -1; for (int cPath = pathIn[x];;) { if (hldPaths[cPath].back() == root || !filled[par[hldPaths[cPath].back()]]) { vToBlank = hldPaths[cPath][highestFilled[cPath]]; break; } else { cPath = pathIn[par[hldPaths[cPath].back()]]; } } // update filld filled[vToBlank] = false; // update bcc & leafset if (vToBlank != root) { if (blankChildCount[par[vToBlank]] == 0) { leafSet.erase({st[par[vToBlank]], par[vToBlank]}); } ++blankChildCount[par[vToBlank]]; } // update HLD --highestFilled[pathIn[vToBlank]]; // update leafset again leafSet.emplace(st[vToBlank], 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 5 ms | 504 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Runtime error | 105 ms | 25836 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Runtime error | 101 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Runtime error | 6 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
5 | Runtime error | 3 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Runtime error | 4 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
7 | Incorrect | 4 ms | 26484 KB | Output isn't correct |
8 | Runtime error | 3 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
9 | Runtime error | 9 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
10 | Runtime error | 23 ms | 26484 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
11 | Runtime error | 124 ms | 27760 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
12 | Runtime error | 99 ms | 28264 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
13 | Runtime error | 94 ms | 28912 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 28912 KB | Output is correct |
2 | Runtime error | 181 ms | 46908 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Runtime error | 150 ms | 47364 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
4 | Runtime error | 52 ms | 47364 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
5 | Runtime error | 46 ms | 47364 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Runtime error | 43 ms | 47364 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
7 | Runtime error | 45 ms | 47364 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
8 | Correct | 51 ms | 47364 KB | Output is correct |
9 | Runtime error | 154 ms | 47908 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
10 | Runtime error | 189 ms | 51220 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
11 | Runtime error | 176 ms | 52208 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
12 | Runtime error | 174 ms | 52208 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
13 | Correct | 164 ms | 52208 KB | Output is correct |
14 | Runtime error | 151 ms | 54004 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 136 ms | 54004 KB | Output isn't correct |
2 | Execution timed out | 1079 ms | 54336 KB | Time limit exceeded |
3 | Correct | 162 ms | 54336 KB | Output is correct |
4 | Runtime error | 144 ms | 54336 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
5 | Runtime error | 179 ms | 54336 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Runtime error | 135 ms | 54336 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
7 | Runtime error | 147 ms | 54336 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
8 | Correct | 140 ms | 54336 KB | Output is correct |
9 | Runtime error | 307 ms | 59572 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
10 | Execution timed out | 1082 ms | 61448 KB | Time limit exceeded |
11 | Execution timed out | 1079 ms | 62240 KB | Time limit exceeded |
12 | Execution timed out | 1083 ms | 62240 KB | Time limit exceeded |
13 | Correct | 227 ms | 64048 KB | Output is correct |
14 | Runtime error | 176 ms | 65684 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 161 ms | 65684 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
2 | Runtime error | 207 ms | 65684 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
3 | Correct | 180 ms | 67232 KB | Output is correct |
4 | Runtime error | 165 ms | 67232 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
5 | Runtime error | 181 ms | 70536 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
6 | Runtime error | 169 ms | 71380 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
7 | Runtime error | 200 ms | 71380 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
8 | Correct | 158 ms | 71420 KB | Output is correct |
9 | Runtime error | 145 ms | 73280 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |