Submission #574499

#	Time	Username	Problem	Language	Result	Execution time	Memory
574499		Sohsoh84	Ball Machine (BOI13_ballmachine)	C++17	16.11 / 100	151 ms	41652 KiB

ballmachine

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define all(x)			(x).begin(),(x).end()
#define X			first
#define Y			second
#define sep			' '
#define endl			'\n'
#define debug(x)		cerr << #x << ": " <<  x << endl;

const ll MAXN = 1e6 + 10;
const ll LOG = 20;

int n, rt, par[MAXN][LOG], q, tin[MAXN], mn[MAXN], f[MAXN], t;
vector<int> adj[MAXN];
priority_queue<int> pq;
bool used[MAXN];

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

void dfs2(int v) {	
	tin[v] = ++t;
	f[t] = v;
	sort(all(adj[v]), [] (int i, int j) {
		return mn[i] < mn[j];
	});

	for (int u : adj[v])
		dfs2(u);
}

inline int add() {
	int v = f[pq.top()];
	pq.pop();

	used[v] = true;
	return v;
}

inline int remove(int v) {
	int ans = 0;
	for (int i = LOG - 1; i >= 0; i--) {
		if (used[par[v][i]]) {
			ans ^= (1 << i);
			v = par[v][i];
		}	
	}

	used[v] = false;
	pq.push(tin[v]);
	return ans;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) {
		cin >> par[i][0];
		rt = (par[i][0] ? rt : i);
		pq.push(i);

		adj[par[i][0]].push_back(i);
	}

	for (int i = 1; i < LOG; i++)
		for (int v = 1; v <= n; v++)
			par[v][i] = par[par[v][i - 1]][i - 1];

	dfs1(rt);
	dfs2(rt);

	while (q--) {
		int c, x;
		cin >> c >> x;

		if (c == 1) {
			int ans = 0;
			while (x--) ans = add();
			cout << ans << endl;
		} else {
			cout << remove(x) << endl;
		}
	}
	return 0;
}

• Subtask 1: 0 / 25
• Subtask 2: 6.428571428571429 / 30
• Subtask 3: 8.571428571428571 / 40
• Subtask 4: 1.1111111111111112 / 5