oj.uz

Submission #71412

# Submission time Handle Problem Language Result Execution time Memory
71412 2018-08-24T13:25:26 Z spacewalker Ball Machine (BOI13_ballmachine) C++14
0 / 100
 215 ms 44348 KB 
#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, &param);
		if (type == 1) {
			int ans = -1;
			for (int rep = 1; rep <= param; ++rep) ans = bm.addBall();
			printf("%d\n", ans + 1);
		} else {
			printf("-1\n"); continue;
			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, &param);
                    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 158 ms 16288 KB Output isn't correct
3 Incorrect 147 ms 16896 KB Output isn't correct
4 Incorrect 2 ms 16896 KB Output isn't correct
5 Incorrect 3 ms 16896 KB Output isn't correct
6 Incorrect 4 ms 16896 KB Output isn't correct
7 Incorrect 4 ms 16896 KB Output isn't correct
8 Incorrect 4 ms 16896 KB Output isn't correct
9 Incorrect 12 ms 16896 KB Output isn't correct
10 Incorrect 23 ms 16896 KB Output isn't correct
11 Incorrect 118 ms 17360 KB Output isn't correct
12 Incorrect 143 ms 17900 KB Output isn't correct
13 Incorrect 141 ms 18316 KB Output isn't correct

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 68 ms 18316 KB Output isn't correct
2 Incorrect 211 ms 29124 KB Output isn't correct
3 Incorrect 181 ms 30036 KB Output isn't correct
4 Incorrect 66 ms 30036 KB Output isn't correct
5 Incorrect 70 ms 30036 KB Output isn't correct
6 Incorrect 78 ms 30036 KB Output isn't correct
7 Incorrect 64 ms 30036 KB Output isn't correct
8 Incorrect 51 ms 30036 KB Output isn't correct
9 Incorrect 176 ms 31332 KB Output isn't correct
10 Incorrect 192 ms 33440 KB Output isn't correct
11 Incorrect 192 ms 34292 KB Output isn't correct
12 Incorrect 171 ms 34292 KB Output isn't correct
13 Incorrect 128 ms 34292 KB Output isn't correct
14 Incorrect 177 ms 35876 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 91 ms 35876 KB Output isn't correct
2 Incorrect 215 ms 35876 KB Output isn't correct
3 Incorrect 106 ms 35876 KB Output isn't correct
4 Incorrect 126 ms 35876 KB Output isn't correct
5 Incorrect 136 ms 35876 KB Output isn't correct
6 Incorrect 145 ms 35876 KB Output isn't correct
7 Incorrect 139 ms 35876 KB Output isn't correct
8 Incorrect 135 ms 35876 KB Output isn't correct
9 Incorrect 205 ms 36932 KB Output isn't correct
10 Incorrect 204 ms 38508 KB Output isn't correct
11 Incorrect 201 ms 38560 KB Output isn't correct
12 Incorrect 206 ms 38560 KB Output isn't correct
13 Incorrect 170 ms 38560 KB Output isn't correct
14 Incorrect 195 ms 39004 KB Output isn't correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 213 ms 39004 KB Output isn't correct
2 Incorrect 188 ms 39004 KB Output isn't correct
3 Incorrect 164 ms 40024 KB Output isn't correct
4 Incorrect 191 ms 40024 KB Output isn't correct
5 Incorrect 183 ms 42032 KB Output isn't correct
6 Incorrect 194 ms 42692 KB Output isn't correct
7 Incorrect 200 ms 42692 KB Output isn't correct
8 Incorrect 188 ms 43112 KB Output isn't correct
9 Incorrect 173 ms 44348 KB Output isn't correct