Submission #49170

#	Time	Username	Problem	Language	Result	Execution time	Memory
49170		aome	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	471 ms	21940 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;

typedef pair<int, int> ii;

int n, q;
int cnt;
int root;
int p[20][N];
int f[N];
int a[N];
bool in[N];
vector<int> G[N];

void dfs1(int u) {
	f[u] = u;
	for (auto v : G[u]) {
		dfs1(v), f[u] = min(f[u], f[v]);
	}
	sort(G[u].begin(), G[u].end(), [&] (int x, int y) {
		return f[x] < f[y];
	});
}

void dfs2(int u) {
	for (auto v : G[u]) dfs2(v); 
	a[u] = cnt--;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> p[0][i];
		if (!p[0][i]) root = i;
		else {
			G[p[0][i]].push_back(i);
		}
	}
	for (int i = 1; i <= 17; ++i) {
		for (int j = 1; j <= n; ++j) {
			p[i][j] = p[i - 1][p[i - 1][j]];
		}
	}
	cnt = n;
	dfs1(root), dfs2(root);
	priority_queue<ii> pq;
	for (int i = 1; i <= n; ++i) pq.push({a[i], i});
	while (q--) {
		int t, x; cin >> t >> x;
		if (t == 2) {
			int res = 0;
			for (int i = 17; i >= 0; --i) {
				if (in[p[i][x]]) res += (1 << i), x = p[i][x];
			}
			cout << res << '\n';
			in[x] = 0, pq.push({a[x], x});
		}
		else {
			int res = 0;
			while (x--) {
				int tmp = pq.top().second; pq.pop();
				res = tmp, in[tmp] = 1;
			}
			cout << res << '\n';
		}
	}
}

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