Submission #870526

#	Time	Username	Problem	Language	Result	Execution time	Memory
870526		Amirmohammad_sh	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	138 ms	28924 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10, lg = 20;
set<int> s;
bool mark[N];
vector<int> adj[N];
int n, q, r, cnt, h[N], mn[N], ft[N], ft1[N], par[N][lg];

bool cmp(int i, int j) {
	return mn[i] < mn[j];
}

void dfs1(int v){
	for (int i = 1; i < lg; i++){
		if (par[v][i - 1] != -1) {
			par[v][i] = par[par[v][i - 1]][i - 1];
		}
	}
	for (auto u: adj[v]){
		h[u] = h[v] + 1;
		dfs1(u);
		mn[v] = min(mn[v], mn[u]);
	}
}

int get_par(int v) {
	for (int i = lg - 1; ~i; i--) {
		if (par[v][i] != -1 && mark[par[v][i]]) {
			v = par[v][i];
		}
	}
	return v;
}

void dfs2(int v){
	for (auto u: adj[v]){
		dfs2(u);
	}
	s.insert(cnt);
	ft[v] = cnt;
	ft1[cnt] = v;
	cnt++;
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	memset(par, -1, sizeof par);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		mn[i] = i;
		par[i][0] = p;
		adj[p].push_back(i);
		if (p == 0) {
			r = i;
		}
	}
	dfs1(r);
	for (int i = 1; i <= n; i++)  {
		sort(adj[i].begin(), adj[i].end(), cmp);
	}
	dfs2(r);
	while(q--) {
		int t;
		cin >> t;
		if (t == 1) {
			int k, v;
			cin >> k;
			while (k--) {
				v = ft1[*s.begin()];
				mark[v] = true;
				s.erase(ft[v]);
			}
			cout << v << "\n";
		}
		else {
			int v;
			cin >> v;
			int u = get_par(v);
			mark[u] = false;
			s.insert(ft[u]);
			cout << h[v] - h[u] << "\n";
		}
	}
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:76:17: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |    cout << v << "\n";
      |                 ^~~~

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