Submission #1122947

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122947		stefanneagu	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	145 ms	34216 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) {
	mps[i] = i;
	for(auto it : in[i]) {
		dfs1(it);
		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) {
	sort(in[i].begin(), in[i].end(), cmp);
	for(auto it : in[i]) {
		dfs2(it);
	}
	to[i] = timp;
	back[timp] = i;
	timp++;
}

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

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);
	}
	dfs1(root);
	dfs2(root);
	for(int i = 1; i <= n; i++) {
		for(auto it : in[i]) {
			adj[to[i]].push_back(to[it]);
		}
	}
	dfs(n);
	int ans = 0;
	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 {
			a = to[a];
			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';
			s.insert(a);
			f[a] = 1;
		}
	}
	return 0;
}

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