Submission #72962

#	Time	Username	Problem	Language	Result	Execution time	Memory
72962		spacewalker	Ball Machine (BOI13_ballmachine)	C++11	16.11 / 100	1079 ms	45624 KiB

ballmachine

#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, trav;
	vector<bool> filled;
	set<int> leafSet;
	int root, t = 0;
	int getInfo(int i, int p, int level) {
		par[i] = p;
		depth[i] = level + 1;
		st[i] = t++;
		trav.push_back(i);
		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]);
		} 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
		int toFillPair = *leafSet.begin();
		leafSet.erase(toFillPair);
		int vToFill = trav[toFillPair];
		// 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]]);
			}
		}
		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]]);
			}
			++blankChildCount[par[vToBlank]];
		}
		// update HLD
		--highestFilled[pathIn[vToBlank]];
		// update leafset again
		leafSet.emplace(st[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, &param);
		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 (stderr)

ballmachine.cpp: In constructor 'BallMachine::BallMachine(std::vector<std::vector<int> >&, int&)':
ballmachine.cpp:13:6: warning: 'BallMachine::root' will be initialized after [-Wreorder]
  int root, t = 0;
      ^~~~
ballmachine.cpp:11:15: warning:   'std::vector<bool> BallMachine::filled' [-Wreorder]
  vector<bool> filled;
               ^~~~~~
ballmachine.cpp:47:2: warning:   when initialized here [-Wreorder]
  BallMachine(vector<vector<int>> &tree, int &root) : tree(tree), par(tree.size()),
  ^~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:96: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:99: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:110: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, &param);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.1111111111111112 / 5