oj.uz

Submission #70986

# Submission time Handle Problem Language Result Execution time Memory
70986 2018-08-24T01:02:42 Z spacewalker Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 353 ms 89816 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]) {
			if (child != p) {
				int childSize = findInfo(child, v, level + 1);
				if (childSize > bchilds) {
					bestChild = child, bchilds = childSize;
				}
				stSize += childSize;
				++childCount[v];
			}
		}
		int pathToAdd = -1;
		if (stSize == 1) {
			pathToAdd = hldPaths.size();
			hldPaths.emplace_back();
			leafSet.emplace(st[v], v);
			highestFilled.emplace_back(-1);
		} 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;
		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)
				|| (!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

ballmachine.cpp: In member function 'int BallMachine::deleteBall(int)':
ballmachine.cpp:70: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:95: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:98: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:109: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 508 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 197 ms 30448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 143 ms 32344 KB Output isn't correct
4 Runtime error 6 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 5 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 5 ms 32344 KB Output isn't correct
8 Runtime error 4 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 8 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 42 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 113 ms 32344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 142 ms 34552 KB Output isn't correct
13 Incorrect 179 ms 35476 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 35476 KB Output is correct
2 Runtime error 185 ms 54304 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Incorrect 176 ms 57436 KB Output isn't correct
4 Runtime error 54 ms 57436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 45 ms 57436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 86 ms 57436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 62 ms 57436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 60 ms 57436 KB Output is correct
9 Runtime error 175 ms 57436 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 192 ms 60236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 242 ms 62408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 243 ms 62408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 173 ms 62408 KB Output is correct
14 Incorrect 191 ms 63672 KB Output isn't correct

Subtask #3
8.57142857143 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 63672 KB Output isn't correct
2 Incorrect 344 ms 64140 KB Output isn't correct
3 Correct 153 ms 64140 KB Output is correct
4 Runtime error 203 ms 64140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 223 ms 64140 KB Output isn't correct
6 Incorrect 216 ms 64140 KB Output isn't correct
7 Runtime error 216 ms 64140 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 179 ms 64140 KB Output is correct
9 Incorrect 326 ms 66976 KB Output isn't correct
10 Incorrect 353 ms 69724 KB Output isn't correct
11 Incorrect 297 ms 71120 KB Output isn't correct
12 Incorrect 299 ms 71120 KB Output isn't correct
13 Correct 196 ms 73016 KB Output is correct
14 Incorrect 350 ms 74992 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 206 ms 77972 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 227 ms 80776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 164 ms 82420 KB Output is correct
4 Runtime error 239 ms 82976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Incorrect 347 ms 85756 KB Output isn't correct
6 Runtime error 186 ms 87236 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 316 ms 87628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 194 ms 88132 KB Output is correct
9 Incorrect 200 ms 89816 KB Output isn't correct