답안 #72962 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72962	2018-08-27T09:58:46 Z	spacewalker	Ball Machine (BOI13_ballmachine)	C++11	16.1111 / 100	1000 ms	45624 KB

ballmachine

#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, trav;
	vector<bool> filled;
	set<int> leafSet;
	int root, t = 0;
	int getInfo(int i, int p, int level) {
		par[i] = p;
		depth[i] = level + 1;
		st[i] = t++;
		trav.push_back(i);
		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]);
		} 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
		int toFillPair = *leafSet.begin();
		leafSet.erase(toFillPair);
		int vToFill = trav[toFillPair];
		// 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]]);
			}
		}
		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]]);
			}
			++blankChildCount[par[vToBlank]];
		}
		// update HLD
		--highestFilled[pathIn[vToBlank]];
		// update leafset again
		leafSet.emplace(st[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:47: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:96: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:99: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:110: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

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	504 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	155 ms	25824 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	115 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	7 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	3 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	4 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Incorrect	5 ms	25916 KB	Output isn't correct
8	Runtime error	4 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
9	Runtime error	7 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	24 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	119 ms	25916 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	105 ms	25972 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Runtime error	115 ms	26088 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #2
6.42857142857 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	67 ms	26088 KB	Output is correct
2	Runtime error	178 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Runtime error	151 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Runtime error	48 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	46 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	52 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	45 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	54 ms	45300 KB	Output is correct
9	Runtime error	159 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Runtime error	200 ms	45300 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
11	Runtime error	179 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
12	Runtime error	176 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
13	Correct	162 ms	45496 KB	Output is correct
14	Runtime error	158 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
8.57142857143 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	109 ms	45496 KB	Output isn't correct
2	Execution timed out	1078 ms	45496 KB	Time limit exceeded
3	Correct	168 ms	45496 KB	Output is correct
4	Runtime error	145 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	154 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	163 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	161 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	171 ms	45496 KB	Output is correct
9	Runtime error	330 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
10	Execution timed out	1079 ms	45496 KB	Time limit exceeded
11	Execution timed out	1077 ms	45496 KB	Time limit exceeded
12	Execution timed out	1072 ms	45496 KB	Time limit exceeded
13	Correct	229 ms	45496 KB	Output is correct
14	Runtime error	181 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
1.11111111111 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	158 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Runtime error	224 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
3	Correct	164 ms	45496 KB	Output is correct
4	Runtime error	163 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Runtime error	157 ms	45496 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
6	Runtime error	170 ms	45624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
7	Runtime error	218 ms	45624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
8	Correct	170 ms	45624 KB	Output is correct
9	Runtime error	141 ms	45624 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

답안 #72962

Compilation message

Subtask #1 0 / 25.0

Subtask #2 6.42857142857 / 30.0

Subtask #3 8.57142857143 / 40.0

Subtask #4 1.11111111111 / 5.0

Subtask #1
0 / 25.0

Subtask #2
6.42857142857 / 30.0

Subtask #3
8.57142857143 / 40.0

Subtask #4
1.11111111111 / 5.0