답안 #71408 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
71408	2018-08-24T13:24:03 Z	spacewalker	Ball Machine (BOI13_ballmachine)	C++14	0 / 100	215 ms	26652 KB

ballmachine

#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);
	return 0;
	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:115: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	Incorrect	4 ms	376 KB	Output isn't correct
2	Incorrect	121 ms	16512 KB	Output isn't correct
3	Incorrect	115 ms	16512 KB	Output isn't correct
4	Incorrect	3 ms	16512 KB	Output isn't correct
5	Incorrect	2 ms	16512 KB	Output isn't correct
6	Incorrect	3 ms	16512 KB	Output isn't correct
7	Incorrect	4 ms	16512 KB	Output isn't correct
8	Incorrect	3 ms	16512 KB	Output isn't correct
9	Incorrect	7 ms	16512 KB	Output isn't correct
10	Incorrect	22 ms	16512 KB	Output isn't correct
11	Incorrect	101 ms	16512 KB	Output isn't correct
12	Incorrect	94 ms	16512 KB	Output isn't correct
13	Incorrect	93 ms	16512 KB	Output isn't correct

Subtask #2
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	19 ms	16512 KB	Output isn't correct
2	Incorrect	162 ms	26524 KB	Output isn't correct
3	Incorrect	185 ms	26528 KB	Output isn't correct
4	Incorrect	47 ms	26528 KB	Output isn't correct
5	Incorrect	54 ms	26528 KB	Output isn't correct
6	Incorrect	50 ms	26528 KB	Output isn't correct
7	Incorrect	47 ms	26528 KB	Output isn't correct
8	Incorrect	18 ms	26528 KB	Output isn't correct
9	Incorrect	188 ms	26528 KB	Output isn't correct
10	Incorrect	198 ms	26528 KB	Output isn't correct
11	Incorrect	179 ms	26532 KB	Output isn't correct
12	Incorrect	152 ms	26532 KB	Output isn't correct
13	Incorrect	131 ms	26532 KB	Output isn't correct
14	Incorrect	148 ms	26532 KB	Output isn't correct

Subtask #3
0 / 40.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	69 ms	26532 KB	Output isn't correct
2	Incorrect	150 ms	26532 KB	Output isn't correct
3	Incorrect	123 ms	26532 KB	Output isn't correct
4	Incorrect	125 ms	26532 KB	Output isn't correct
5	Incorrect	158 ms	26532 KB	Output isn't correct
6	Incorrect	144 ms	26532 KB	Output isn't correct
7	Incorrect	115 ms	26532 KB	Output isn't correct
8	Incorrect	90 ms	26532 KB	Output isn't correct
9	Incorrect	131 ms	26532 KB	Output isn't correct
10	Incorrect	140 ms	26548 KB	Output isn't correct
11	Incorrect	171 ms	26620 KB	Output isn't correct
12	Incorrect	178 ms	26620 KB	Output isn't correct
13	Incorrect	163 ms	26620 KB	Output isn't correct
14	Incorrect	160 ms	26620 KB	Output isn't correct

Subtask #4
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	168 ms	26620 KB	Output isn't correct
2	Incorrect	167 ms	26620 KB	Output isn't correct
3	Incorrect	215 ms	26620 KB	Output isn't correct
4	Incorrect	168 ms	26620 KB	Output isn't correct
5	Incorrect	195 ms	26620 KB	Output isn't correct
6	Incorrect	191 ms	26620 KB	Output isn't correct
7	Incorrect	206 ms	26620 KB	Output isn't correct
8	Incorrect	150 ms	26620 KB	Output isn't correct
9	Incorrect	165 ms	26652 KB	Output isn't correct

답안 #71408

Compilation message

Subtask #1 0 / 25.0

Subtask #2 0 / 30.0

Subtask #3 0 / 40.0

Subtask #4 0 / 5.0

Subtask #1
0 / 25.0

Subtask #2
0 / 30.0

Subtask #3
0 / 40.0

Subtask #4
0 / 5.0