Submission #282991

#	Time	Username	Problem	Language	Result	Execution time	Memory
282991		usuyus	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	630 ms	31260 KiB

ballmachine

#include <bits/stdc++.h>
#define N 100001
#define L 21
using namespace std;

int n, q, root, lg[N];
int par[N][L], mn[N], revord[N];
vector<int> tree[N], ord;

struct comp {
	bool operator() (int x, int y) const {
		return revord[x] < revord[y];
	}
};

set<int, comp> st;
bool vis[N];

int min_dfs(int node) {
	int res = node;
	for (int child : tree[node]) {
		res = min(res, min_dfs(child));
	}
	return mn[node] = res;
}

void ord_dfs(int node) {
	vector<pair<int, int>> w;
	for (int child : tree[node]) {
		w.push_back(make_pair(mn[child], child));
	}
	sort(w.begin(), w.end());
	for (auto child : w) ord_dfs(child.second);
	ord.push_back(node);
	revord[node] = ord.size()-1;
}

void fill_par() {
	for (int l=1; l<L; l++) {
		for (int i=1; i<=n; i++) {
			par[i][l] = par[par[i][l-1]][l-1];
		}
	}
}

int main() {
	cin>>n>>q; lg[0] = -1;
	for (int i=1; i<=n; i++) {
		int p; cin>>p;
		if (p == 0) root = i;
		tree[p].push_back(i);
		par[i][0] = p;
		lg[i] = lg[i/2] + 1;
	}

	min_dfs(root);
	ord_dfs(root);
	fill_par();

	for (int i=1; i<=n; i++) st.insert(i);

	while (q--) {
		int t; cin>>t;
		if (t == 1) {
			int k; cin>>k;
			while (k--) {
				int x = *st.begin();
				vis[x] = 1;
				if (k == 0) cout<<x<<endl;
				st.erase(st.begin());
			}
		} else {
			int x; cin>>x;
			int y = x, len = 0;

			for (int l=L-1; l>=0; l--) {
				if (vis[par[y][l]]) y = par[y][l], len += 1<<l;
			}

			vis[y] = 0;
			st.insert(y);
			cout<<len<<endl;
		}
	}
}

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