제출 #1122945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1122945		stefanneagu	Ball Machine (BOI13_ballmachine)	C++20	23.08 / 100	1097 ms	33608 KiB

ballmachine

#include <bits/stdc++.h>
 
using namespace std;
 
const int nmax = 1e5 + 5;
 
set<int> s;
vector<int> in[nmax], adj[nmax];
bool f[nmax];
int mps[nmax], to[nmax], back[nmax];
int up[nmax][17], d[nmax];

void dfs1(int i, int tata = 0) {
	mps[i] = i;
	for(auto it : in[i]) {
		if(it != tata) {
			dfs1(it, i);
			mps[i] = min(mps[i], mps[it]);
		}
	}
}

int timp = 1;

bool cmp(int a, int b) {
	return mps[a] < mps[b];
}

void dfs2(int i, int tata = 0) {
	sort(in[i].begin(), in[i].end(), cmp);
	for(auto it : in[i]) {
		if(it != tata) {
			dfs2(it, i);
		}
	}
	to[i] = timp;
	back[timp] = i;
	timp++;
}

void dfs(int i, int tata = 0) {
	up[i][0] = tata;
	for(int j = 1; (1 << j) <= d[i]; j++) {
		up[i][j] = up[up[i][j - 1]][j - 1];
	}
	for(auto it : adj[i]) {
		if(it != tata) {
			d[it] = d[i] + 1;
			dfs(it, i);
		}
	}
}

int qry(int a) {
	int ans = 0;
	for(int i = 16; i >= 0; i--) {
		if((1 << i) <= d[a] && f[up[a][i]] == 0) {
			a = up[a][i];
			ans += (1 << i);
		}
	}
	cout << ans << '\n';
	return a;
}
	

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n, q, root = -1;
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		s.insert(i);
		f[i] = 1;
		int a;
		cin >> a;
		if(a == 0) {
			root = i;
			continue;
		}
		in[a].push_back(i);
		in[i].push_back(a);
	}
	dfs1(root);
	dfs2(root);
	for(int i = 1; i <= n; i++) {
		for(auto it : in[i]) {
			adj[to[i]].push_back(to[it]);
			adj[to[it]].push_back(to[i]);
		}
	}
	dfs(n);
	while(q--) {
		int t, a;
		cin >> t >> a;
		if(t == 1) {
			int ult = 0;
			while(a--) {
				if(s.empty()) {
					break;
				}
				ult = *s.begin();
				f[ult] = 0;
				s.erase(ult);
			}
			cout << back[ult] << '\n';
		} else {
			int x = qry(to[a]);
			s.insert(x);
			f[x] = 1;
		}
	}
	return 0;
}

• Subtask 1: 15.3846 / 25
• Subtask 2: 4.2857 / 30
• Subtask 3: 2.8571 / 40
• Subtask 4: 0.5556 / 5