oj.uz

답안 #84116

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84116 2018-11-13T04:42:08 Z shoemakerjo Ball Machine (BOI13_ballmachine) C++14
100 / 100
 282 ms 74736 KB 
#include <bits/stdc++.h>

using namespace std;
#define maxn 100010
#define pii pair<int, int>

int N, Q;
int par[18][maxn];

vector<int> ch[maxn];
vector<int> order;
int rt;
int minsub[maxn];
bool isin[maxn];
int myindo[maxn];

void getorder(int u) {
	vector<pii> nch;
	for (int v : ch[u]) {
		nch.push_back(pii(minsub[v], v));
	}
	sort(nch.begin(), nch.end());
	for (pii vp : nch) {
		getorder(vp.second);
	}
	order.push_back(u);
}

void godown(int u) {
	minsub[u] = u;
	for (int v : ch[u]) {
		godown(v);
		minsub[u] = min(minsub[u], minsub[v]);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> par[0][i];
		ch[par[0][i]].push_back(i);
	}
	rt = ch[0][0];
	godown(rt);
	getorder(rt);
	for (int i = 1; i < 18; i++) {
		for (int j = 1; j <= N; j++) {
			par[i][j] = par[i-1][par[i-1][j]];
		}
	}
	int tp, x;

	set<pii> open;
	int ct = 0;
	for (int v : order) {
		open.insert(pii(ct++, v));
	}
	for (int i = 0; i < order.size(); i++) {
		myindo[order[i]] = i;
	}

	while (Q--) {
		cin >> tp >> x;
		if (tp == 1) {
			int ans = -1;
			while (x--) {
				pii cur = *(open.begin());
				open.erase(open.begin());
				isin[cur.second] = true;
				ans = cur.second;
			}
			cout << ans << '\n';
		}
		else {
			int tempo = x;
			int numfall = 0;
			for (int i = 17; i >= 0; i--) {
				if (isin[par[i][tempo]]) {
					numfall += (1 << i);
					tempo  = par[i][tempo];
				}
			}
			cout << numfall << '\n';
			isin[tempo] = false;
			open.insert(pii(myindo[tempo], tempo));
		}	
	}
	cout.flush();


}

Compilation message

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < order.size(); i++) {
                  ~~^~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 2808 KB Output is correct
2 Correct 171 ms 13708 KB Output is correct
3 Correct 84 ms 14896 KB Output is correct
4 Correct 5 ms 14896 KB Output is correct
5 Correct 5 ms 14896 KB Output is correct
6 Correct 5 ms 14896 KB Output is correct
7 Correct 5 ms 14896 KB Output is correct
8 Correct 5 ms 14896 KB Output is correct
9 Correct 12 ms 14896 KB Output is correct
10 Correct 32 ms 14896 KB Output is correct
11 Correct 171 ms 16732 KB Output is correct
12 Correct 88 ms 17512 KB Output is correct
13 Correct 125 ms 18596 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 18596 KB Output is correct
2 Correct 212 ms 30684 KB Output is correct
3 Correct 110 ms 30684 KB Output is correct
4 Correct 82 ms 30684 KB Output is correct
5 Correct 80 ms 30684 KB Output is correct
6 Correct 73 ms 30684 KB Output is correct
7 Correct 79 ms 30684 KB Output is correct
8 Correct 44 ms 30684 KB Output is correct
9 Correct 212 ms 37064 KB Output is correct
10 Correct 200 ms 37932 KB Output is correct
11 Correct 169 ms 39152 KB Output is correct
12 Correct 204 ms 39152 KB Output is correct
13 Correct 142 ms 44984 KB Output is correct
14 Correct 107 ms 44984 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 101 ms 44984 KB Output is correct
2 Correct 282 ms 44984 KB Output is correct
3 Correct 200 ms 46612 KB Output is correct
4 Correct 170 ms 46612 KB Output is correct
5 Correct 181 ms 46612 KB Output is correct
6 Correct 203 ms 46612 KB Output is correct
7 Correct 179 ms 46612 KB Output is correct
8 Correct 173 ms 51308 KB Output is correct
9 Correct 279 ms 52228 KB Output is correct
10 Correct 271 ms 53124 KB Output is correct
11 Correct 259 ms 54480 KB Output is correct
12 Correct 258 ms 54480 KB Output is correct
13 Correct 276 ms 63224 KB Output is correct
14 Correct 239 ms 63224 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 63224 KB Output is correct
2 Correct 257 ms 63224 KB Output is correct
3 Correct 171 ms 68232 KB Output is correct
4 Correct 226 ms 68232 KB Output is correct
5 Correct 241 ms 68232 KB Output is correct
6 Correct 172 ms 68232 KB Output is correct
7 Correct 233 ms 68232 KB Output is correct
8 Correct 169 ms 74736 KB Output is correct
9 Correct 115 ms 74736 KB Output is correct