Submission #1244995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244995		kaiboy	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	90 ms	14148 KiB

ballmachine

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 100000;

int *ej[N], eo[N], dd[N], pp[N], qq[N], aa[N], hh[N], pq[N], iq[N + 1], pq_cnt;

void append(int i, int j) {
	int o = eo[i]++;
	if (!o)
		ej[i] = (int *) malloc(sizeof *ej[i]);
	else if (!(o & o - 1))
		ej[i] = (int *) realloc(ej[i], (o << 1) * sizeof *ej[i]);
	ej[i][o] = j;
}

int dfs(int p, int i, int d) {
	dd[i] = d++, pp[i] = qq[i] = p;
	if (dd[pp[i]] - dd[qq[pp[i]]] == dd[qq[pp[i]]] - dd[qq[qq[pp[i]]]])
		qq[i] = qq[qq[pp[i]]];
	int a = i;
	for (int o = 0; o < eo[i]; o++)
		a = min(a, dfs(i, ej[i][o], d));
	return aa[i] = a;
}

void dfs(int i) {
	static int h = 0;
	for (int o = 0; o < eo[i]; o++)
		dfs(ej[i][o]);
	hh[i] = h++;
}

bool lt(int i, int j) {
	return hh[i] < hh[j];
}

int p2(int p) {
	return (p <<= 1) > pq_cnt ? 0 : p ^ (p < pq_cnt && lt(iq[p ^ 1], iq[p]));
}

void pq_up(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p >> 1) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int j, p, q;
	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++pq_cnt] = i;
}

void pq_add(int i) {
	pq[i] = ++pq_cnt, pq_up(i);
}

int pq_remove_first() {
	int i = iq[1], j = iq[pq_cnt--];
	if (i != j)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int search(int i) {
	while (pp[i] != i && !pq[pp[i]])
		i = !pq[qq[i]] ? qq[i] : pp[i];
	return i;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	int n, q; cin >> n >> q;
	int r = -1;
	for (int i = 0; i < n; i++) {
		int p; cin >> p, p--;
		if (p == -1)
			r = i;
		else
			append(p, i);
	}
	dfs(r, r, 0);
	for (int i = 0; i < n; i++)
		sort(ej[i], ej[i] + eo[i], [] (int j0, int j1) { return aa[j0] < aa[j1]; });
	dfs(r);
	for (int i = 0; i < n; i++)
		pq_add_last(i);
	for (int p = pq_cnt >> 1; p; p--)
		pq_dn(iq[p]);
	while (q--) {
		int t; cin >> t;
		if (t == 1) {
			int k; cin >> k;
			while (k--) {
				int i = pq_remove_first();
				if (!k)
					cout << i + 1 << '\n';
			}
		} else {
			int i; cin >> i, i--;
			int p = search(i); pq_add(p);
			cout << dd[i] - dd[p] << '\n';
		}
	}
	return 0;
}

• Subtask 1: 25 / 25
• Subtask 2: 30 / 30
• Subtask 3: 40 / 40
• Subtask 4: 5 / 5