Submission #84116

#	Time	Username	Problem	Language	Result	Execution time	Memory
84116		shoemakerjo	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	282 ms	74736 KiB

ballmachine

#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 (stderr)

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 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5