Submission #1122690

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122690		stefanneagu	Ball Machine (BOI13_ballmachine)	C++20	0 / 100	1098 ms	40796 KiB

ballmachine

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

void dfs1(int i, int tata = 0) {
	mps[i] = v[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) {
	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] && s.find(up[a][i]) == s.end()) {
			a = up[a][i];
			ans += (1 << i);
		}
	}
	cout << ans << '\n';
	return a;
}
	

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie();
	cout.tie();
	int n, q, root = -1;
	cin >> n >> q;
	for(int i = 1; i <= n; i++) {
		s.insert(i);
		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--) {
				ult = *s.begin();
				s.erase(ult);
			}
			cout << back[ult] << '\n';
		} else {
			s.insert(qry(to[a]));
		}
	}
	return 0;
}

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