Submission #1126777

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126777		Halym2007	Ball Machine (BOI13_ballmachine)	C++17	100 / 100	136 ms	29356 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sz size()
#define ff first
#define ss second
#define pb push_back
#define pii pair <int, int>
#define dur exit(0)
#define dur1 return(0)
const int N = 2e5 + 5;
const int LOG = 17;
int qu[N], o, p[N][LOG], ball[N], val[N], bal[N];
set <pii> yok;
vector <int> v[N];

bool cmp (int x, int y) {
	if (val[x] < val[y]) return 1;
	return 0;
}

void dfs (int x, int par) {
	val[x] = x;
	for (int i : v[x]) {
		if (i == par) continue;
		dfs (i, x);
		val[x] = min (val[x], val[i]);
	} 
	sort (v[x].begin(), v[x].end(), cmp);
}


void dfs1 (int x, int par) {
	for (int i : v[x]) {
		if (i == par) continue;
		dfs1 (i, x);
	}
//	cout << "-- > " << x << " " << par << endl;
	qu[++o] = x;
}

pii cykar (int x) {
	int ret = 0;
	for (int i = LOG - 1; i >= 0; i--) {
//		cout << i << " " << p[x][i] << " " << ball[p[x][i]] << " " << x << endl;
		if (ball[p[x][i]]) {
			x = p[x][i];
			ret += (1 << i);
		}
	}
//	dur;
	return {x, ret};
}

int main () {
//	freopen ("input.txt", "r", stdin);
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n, q, par;
	cin >> n >> q;
	for (int i = 1; i <= n; ++i) {
		cin >> p[i][0];
		if (p[i][0] != 0) {
			v[p[i][0]].pb (i);
			v[i].pb (p[i][0]);
		}
		else {
			par = i;
		}
	}
	dfs (par, -1);
	dfs1 (par, -1);
	for (int i = 1; i < LOG; ++i) {
		for (int j = 1; j <= n; ++j) {
			// n + 2^(15)
			p[j][i] = p[p[j][i - 1]][i - 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		yok.insert ({i, qu[i]});
	}
//	for (int i = 1; i <= n; ++i) {
//		cout << i << " -- > ";
//		for (int j : v[i]) {
//			cout << j << " ";
//		}
//		cout << "\n";
//	}
//	cout << "\nyzygiderlilik --> : \n";
	for (int i = 1; i <= n; ++i) {
		bal[qu[i]] = i;
//		cout << qu[i] << " ";
	}
//	cout << "\n";
//	return 0;
	while ( q-- ) {
		int type, x;
		cin >> type >> x;
		if (type == 1) {
			int jog = -1;
			for (int i = 1; i <= x; ++i) {
				pii tr = *yok.begin();
				yok.erase (yok.begin());
				ball[tr.ss] = 1;
				jog = tr.ss;
			}
			cout << jog << "\n";
		}
		else {
			pii x1 = cykar (x);
			cout << x1.ss << "\n";
			ball[x1.ff] = 0;
			yok.insert ({bal[x1.ff], x1.ff});
		}
	}
}

/*
1 0
2-1
3-2
4-2
5-3
6-3
7-4
8-6
*/

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