oj.uz

답안 #72978

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72978 2018-08-27T11:46:41 Z spacewalker Ball Machine (BOI13_ballmachine) C++14
16.1111 / 100
 344 ms 46064 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, 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;
				}
				stSize += 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:48: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:97: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:100: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:111: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 3 ms 504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 122 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 110 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 6 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 2 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 3 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 4 ms 25716 KB Output isn't correct
8 Runtime error 4 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 7 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 23 ms 25716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 111 ms 25928 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 97 ms 25944 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 107 ms 25988 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 25988 KB Output is correct
2 Runtime error 172 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 164 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 38 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 35 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 45 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 41 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 51 ms 43524 KB Output is correct
9 Runtime error 198 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 166 ms 43524 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 178 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 187 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 167 ms 43620 KB Output is correct
14 Runtime error 142 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
8.57142857143 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 43620 KB Output isn't correct
2 Runtime error 292 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 148 ms 43620 KB Output is correct
4 Runtime error 144 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 141 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 151 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 153 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 155 ms 43620 KB Output is correct
9 Runtime error 289 ms 43620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 344 ms 44968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 341 ms 45708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 290 ms 45708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Correct 254 ms 45708 KB Output is correct
14 Runtime error 217 ms 45708 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 221 ms 45708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 177 ms 45708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 175 ms 45708 KB Output is correct
4 Runtime error 193 ms 45708 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 166 ms 45836 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 162 ms 46064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 222 ms 46064 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Correct 179 ms 46064 KB Output is correct
9 Runtime error 133 ms 46064 KB Execution killed with signal 11 (could be triggered by violating memory limits)