Submission #1125714

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125714		Muhammet	Ball Machine (BOI13_ballmachine)	C++20	100 / 100	200 ms	39052 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

#define SZ(s) (int)s.size()
#define ff first
#define ss second

int n, q;

vector <vector <int>> v, sp;

vector <int> m, v1, b, vis;

void dfs(int x, int y){
	m[x] = x;
	for(auto i : v[x]){
		if(i == y) continue;
		dfs(i, x);
		m[x] = min(m[x], m[i]);
	}
	return;
}

void df(int x, int y){
	vector <pair<int,int>> v2;
	for(auto i : v[x]){
		if(i == y) continue;
		v2.push_back({m[i], i});
	}
	sort(v2.begin(), v2.end());
	for(int i = 0; i < SZ(v2); i++){
		df(v2[i].ss, x);
	}
	v1.push_back(x);
}

int d(int x){
	int cnt = 0;
	for(int i = 20; i >= 0; i--){
		int k = sp[x][i];
		if(vis[k] == 1) x = k, cnt += (1<<i);
	}
	cout << cnt << "\n";
	return x;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);

	cin >> n >> q;
	int root = 1;
	v.resize(n+1), m.resize(n+1);
	sp.resize(n+1, vector <int> (25));
	vector <int> a(n+1);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		sp[i][0] = a[i];
		if(a[i] == 0) root = i;
		else {
			v[a[i]].push_back(i);
			v[i].push_back(a[i]);
		}
	}
	dfs(root, 0);
	df(root, 0);
	set <pair<int,int>> s;
	b.resize(n+1), vis.resize(n+1,0);
	for(int i = 0; i < SZ(v1); i++){
		s.insert({i, v1[i]});
		b[v1[i]] = i;
	}
	for(int j = 1; j <= 20; j++){
		for(int i = 1; i <= n; i++){
			sp[i][j] = sp[sp[i][j-1]][j-1];
		}
	}
	while(q--){
		int t, x;
		cin >> t >> x;
		if(t == 1){
			int k;
			while(x--){
				k = (*s.begin()).ss;
				vis[k] = 1;
				s.erase(s.begin());
			}
			cout << k << '\n';
		}
		else {
			int k = d(x);
			vis[k] = 0;
			s.insert({b[k], k});
		}
	}
}

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