제출 #1290030

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1290030		kam	Ball Machine (BOI13_ballmachine)	C++20	16.11 / 100	1096 ms	29080 KiB

ballmachine

#include<unordered_map>
#include<unordered_set>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<cassert>
#include<numeric>
#include<vector>
#include<string>
#include<chrono>
#include<random>
#include<stack>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<ios>
using namespace std;
using ll = long long;
vector<vector<int>>gp,up;
vector<int>sub, srt, black, rev;
int qq = 0, n, sz=21;

bool cm(int& a, int& b) {
	return sub[a] < sub[b];
}

void build(int u, int p) {
	up[u][0] = p;
	for (int i = 1; i < sz; i++) {
		if (up[u][i - 1] == -1) break;
		up[u][i] = up[up[u][i - 1]][i - 1];
	}
	for (int& v : gp[u]) {
		if (v == p) continue;
		build(v, u);
	}
}

void dfs(int u, int p) {
	for (int& v : gp[u]) {
		if (v == p) continue;
		dfs(v, u);
		sub[v] = min(sub[v], sub[u]);
	}
}

void make(int u, int p) {
	for (int& v : gp[u]) {
		if (v == p) continue;
		make(v, u);
	}
	rev[u] = qq;
	srt[qq++] = u + 1;
}

vector<int> get(int u) {
	int res = 0;
	for (int i = sz - 1; i >= 0; i--) {
		if (up[u][i] == -1)continue;
		if (black[up[u][i]]) {
			u = up[u][i], res += (1 << i);
		}
	}
	return { u,res };
}

void solve()
{
	int q; cin >> n >> q;
	int root = 0;
	sub = srt = black = rev = vector<int>(n);
	gp = vector<vector<int>>(n);
	for (int i = 0; i < n; i++) {
		int x; cin >> x;
		if (x == 0) {
			root = i;
			continue;
		}
		gp[i].push_back(--x);
		gp[x].push_back(i);
	}
	for (int i = 0; i < n; i++)sub[i] = i;
	dfs(root, -1);
	
	for (int i = 0; i < n; i++) sort(begin(gp[i]), end(gp[i]), cm);
	make(root, -1);

	set<pair<int, int>>st;
	for (int i = 0; i < n; i++)st.insert({ i,srt[i] });

	up = vector<vector<int>>(n, vector<int>(sz, -1));
	build(root, -1);
	
	while (q--) {
		int t, k; cin >> t >> k;
		if (t == 1) {
			int res = 0;
			while (k--) {
				pair<int, int> ab = *st.begin();
				st.erase(st.begin());
				black[ab.second - 1] = true;
				res = ab.second;
			}
			cout << res << endl;
			continue;
		}
		vector<int>lavaxper = get(k - 1);
		black[lavaxper[0]] = false;
		st.insert({ rev[lavaxper[0]], lavaxper[0] + 1 });
		cout << lavaxper[1] << endl;
	}
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);

	//freopen("b3.in", "r", stdin);
	//freopen("b3.out", "w", stdout);

	//signed _; cin >> _; while (_--)
	solve();
}

• Subtask 1: 0 / 25
• Subtask 2: 6.4286 / 30
• Subtask 3: 8.5714 / 40
• Subtask 4: 1.1111 / 5