Submission #71382

#	Time	Username	Problem	Language	Result	Execution time	Memory
71382		spacewalker	Ball Machine (BOI13_ballmachine)	C++14	16.11 / 100	386 ms	52896 KiB

ballmachine

#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, &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 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, &param);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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