제출 #49169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
49169		aome	Ball Machine (BOI13_ballmachine)	C++17	41.92 / 100	451 ms	22396 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 h[N];
int a[N];
bool in[N];
vector<int> G[N];

void dfs1(int u) {
	f[u] = u;
	for (auto v : G[u]) {
		h[v] = h[u] + 1, 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]) p[0][i] = 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 (h[x] >= (1 << i) && in[p[i][x]]) {
					x = p[i][x], res += (1 << i);
				}
			}
			cout << res << '\n';
			in[x] = 0, pq.push({x, a[x]});
		}
		else {
			int res = 0;
			while (x--) {
				int tmp = pq.top().second; pq.pop();
				res = tmp, in[tmp] = 1;
			}
			cout << res << '\n';
		}
	}
}

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