oj.uz

Submission #72957

# Submission time Handle Problem Language Result Execution time Memory
72957 2018-08-27T09:51:27 Z spacewalker Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 1000 ms 73280 KB 
#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;
	vector<bool> filled;
	set<pair<int, int>> leafSet;
	int root, t = 0;
	int getInfo(int i, int p, int level) {
		par[i] = p;
		depth[i] = level + 1;
		st[i] = t++;
		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], 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
		auto toFillPair = *leafSet.begin();
		leafSet.erase(toFillPair);
		int vToFill = toFillPair.second;
		// 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]], 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]], par[vToBlank]});
			}
			++blankChildCount[par[vToBlank]];
		}
		// update HLD
		--highestFilled[pathIn[vToBlank]];
		// update leafset again
		leafSet.emplace(st[vToBlank], 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 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:46: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: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 5 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 105 ms 25836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 101 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 3 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 4 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 4 ms 26484 KB Output isn't correct
8 Runtime error 3 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 9 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 23 ms 26484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 124 ms 27760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 99 ms 28264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 94 ms 28912 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 54 ms 28912 KB Output is correct
2 Runtime error 181 ms 46908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 150 ms 47364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 52 ms 47364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 46 ms 47364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 43 ms 47364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 45 ms 47364 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 51 ms 47364 KB Output is correct
9 Runtime error 154 ms 47908 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 189 ms 51220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 176 ms 52208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 174 ms 52208 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 164 ms 52208 KB Output is correct
14 Runtime error 151 ms 54004 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 136 ms 54004 KB Output isn't correct
2 Execution timed out 1079 ms 54336 KB Time limit exceeded
3 Correct 162 ms 54336 KB Output is correct
4 Runtime error 144 ms 54336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 179 ms 54336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 135 ms 54336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 147 ms 54336 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 140 ms 54336 KB Output is correct
9 Runtime error 307 ms 59572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Execution timed out 1082 ms 61448 KB Time limit exceeded
11 Execution timed out 1079 ms 62240 KB Time limit exceeded
12 Execution timed out 1083 ms 62240 KB Time limit exceeded
13 Correct 227 ms 64048 KB Output is correct
14 Runtime error 176 ms 65684 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 161 ms 65684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 207 ms 65684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 180 ms 67232 KB Output is correct
4 Runtime error 165 ms 67232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 181 ms 70536 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 169 ms 71380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 200 ms 71380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 158 ms 71420 KB Output is correct
9 Runtime error 145 ms 73280 KB Execution killed with signal 11 (could be triggered by violating memory limits)