Submission #872225

#	Time	Username	Problem	Language	Result	Execution time	Memory
872225		vjudge1	Ball Machine (BOI13_ballmachine)	C++17	40.24 / 100	1079 ms	131072 KiB

ballmachine

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

typedef pair<int, int> pii;

const int N = 1e5 + 7, SQ = 320;
int n, q, s, t, root, h[N], st[N], sz[N], mn[N], indx[N], it[N];
pii tree[N];
vector<int> ad[N];
set<pii> ver, one[N], sq[SQ];

void input() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int p;
		cin >> p;
		p--;
		if (p < 0)
			root = i;
		else
			ad[p].push_back(i);
	}
}

void dfs(int v) {
	mn[v] = v;
	for (int u: ad[v]) {
		dfs(u);
		mn[v] = min(mn[v], mn[u]);
	}
}

bool cmp(int u, int v) {
	return mn[u] < mn[v];
}

void dfs2(int v) {
	st[v] = s++;
	sz[v] = 1;
	for (int u: ad[v]) {
		h[u] = h[v] + 1;
		dfs2(u);
		sz[v] += sz[u];
	}
	indx[v] = t++;	
}

void secondProcess() {
	for (int i = 0; i < n; i++)
		tree[i] = {st[i], i};
	sort(tree, tree + n);
	for (int i = 0; i < n; i++)
		it[tree[i].second] = i;
	for (int i = 0; i < n; i++)
		ver.insert({indx[i], i});
}

void addTo(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++) 
		if (i % SQ || i + SQ > it[v] + sz[v])
			one[i].insert({h[v], v});
		else {
			sq[i / SQ].insert({h[v], v});
			i += SQ - 1;
		}
}

void toErase(int v) {
	for (int i = it[v]; i < it[v] + sz[v]; i++)
		if (i % SQ || i + SQ > it[v] + sz[v])
			one[i].erase({h[v], v});
		else {
			sq[i / SQ].erase({h[v], v});
			i += SQ - 1;
		}
}

void add(int x) {	
	while (x--) {
		pii p = *ver.begin();
		addTo(p.second);
		ver.erase(ver.begin());
		if (x == 0)
			cout << p.second + 1 << '\n';
	}
}

void output(int v) {
	int p = 0, hi = INT_MAX, i = it[v];
	if (one[i].size()) {
		p = (*one[i].begin()).second;
		hi = h[(*one[i].begin()).second];
	}
	if (sq[i / SQ].size() && h[(*sq[i / SQ].begin()).second] < hi)
		p = (*sq[i / SQ].begin()).second;
	cout << h[v] - h[p] << '\n';
	ver.insert({indx[p], p});
	toErase(p);
}

int main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	input();
	dfs(root);
	for (int i = 0; i < n; i++)
		sort(ad[i].begin(), ad[i].end(), cmp);
	dfs2(root);
	secondProcess();
	while (q--) {
		int t, v;
		cin >> t >> v;
		if (t == 1)
			add(v);
		else {
			v--;
			output(v);
		}
	}
}

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