oj.uz

Submission #71404

# Submission time Handle Problem Language Result Execution time Memory
71404 2018-08-24T13:20:56 Z spacewalker Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 416 ms 50288 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("%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 Runtime error 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 112 ms 29232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 102 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 5 ms 30684 KB Output isn't correct
8 Runtime error 5 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 9 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 28 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 139 ms 30684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 113 ms 31068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 104 ms 31068 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 31068 KB Output is correct
2 Runtime error 216 ms 47652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 177 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 44 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 40 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 41 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 43 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 59 ms 50252 KB Output is correct
9 Runtime error 212 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 193 ms 50252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 222 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 170 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 164 ms 50256 KB Output is correct
14 Runtime error 176 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 112 ms 50256 KB Output isn't correct
2 Runtime error 283 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 168 ms 50256 KB Output is correct
4 Runtime error 155 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 166 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 143 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 146 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 173 ms 50256 KB Output is correct
9 Runtime error 325 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 344 ms 50256 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 416 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 304 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 267 ms 50288 KB Output is correct
14 Runtime error 208 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 181 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 198 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 181 ms 50288 KB Output is correct
4 Runtime error 170 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 194 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 175 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 225 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 189 ms 50288 KB Output is correct
9 Runtime error 186 ms 50288 KB Execution killed with signal 11 (could be triggered by violating memory limits)