Submission #870197

#	Time	Username	Problem	Language	Result	Execution time	Memory
870197		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	663 ms	43336 KiB

ballmachine

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

const int N = 1e5 + 5, lg = 20;
vector<int> G[N], G2[N];
int n, q, spt[N][lg], h[N], dp[N], s[N], root, a[N];
set<int> S;
map<int, int> mp, mp2;
bool ball[N];

void in() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		int p;
		cin >> p;
		a[i] = p;
		if (!p)
			root = i;
		G[i].push_back(p);
		G[p].push_back(i);
	}
}

void dfs(int u = root, int p = 0) {
	spt[u][0] = p;
	dp[u] = u;
	for (int j = 1; j < lg; j++)
		spt[u][j] = spt[spt[u][j - 1]][j - 1];
	for (int v : G[u])
		if (v != p) {
			h[v] = h[u] + 1;
			dfs(v, u);
			dp[u] = min(dp[u], dp[v]);
		}
}

void dfs2(int u = mp2[root], int p = 0) {
	spt[u][0] = p;
	for (int j = 1; j < lg; j++)
		spt[u][j] = spt[spt[u][j - 1]][j - 1];
	for (int v : G2[u])
		if (v != p) {
			h[v] = h[u] + 1;
			dfs2(v, u);
		}
}

int get_par(int u, int x) {
	for (int i = 0; i < lg; i++)
		if ((x >> i) & 1)
			u = spt[u][i];
	return u;
}

int lca(int u, int v) {
	if (h[u] < h[v])
		swap(u, v);
	u = get_par(u, h[u] - h[v]);
	if (u == v)
		return v;
	for (int i = lg - 1; ~i; i--)
		if (spt[v][i] != spt[u][i])
			u = spt[u][i], v = spt[v][i];
	return spt[u][0];
}

bool cmp(const int &a, const int &b) {
	int v = a;
	int u = b;
	int anc = lca(u, v);
	if (anc == v)
		return false;
	if (anc == u)
		return true;	
	v = get_par(v, h[v] - h[anc] - 1);
	u = get_par(u, h[u] - h[anc] - 1);
	return dp[v] < dp[u];
}

void rem(int k) {
	k = mp2[k];
	int u = k;
	for (int i = lg - 1; ~i; i--)
		if (ball[spt[k][i]])
			k = spt[k][i];
	ball[k] = false;
	S.insert(k);
	cout << h[u] - h[k] << endl;
}

void add(int k) {
	int l;
	while(k--) {
		l = *S.begin();
		ball[l] = true;
		S.erase(l);
	}
	cout << mp[l] << endl;
}

void pre() {
	dfs();
	for (int i = 1; i <= n; i++)
		s[i] = i;
	sort(s + 1, s + 1 + n, cmp);
	for (int i = 1; i <= n; i++)
		mp[i] = s[i], mp2[s[i]] = i;
	mp[0] = mp2[0] = 0;
	for (int i = 1; i <= n; i++)
		S.insert(i);
	for (int i = 1; i <= n; i++) {
		a[i] = mp2[a[i]];
		G2[mp2[i]].push_back(a[i]);
		G2[a[i]].push_back(mp2[i]);
		h[i] = 0;
	}
	memset(spt, 0, sizeof spt);
	dfs2();
}

void Q() {
	while(q--) {
		int T, k;
		cin >> T >> k;
		if(T == 1)
			add(k);
		else
			rem(k);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	in();
	pre();
	Q();
}

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