oj.uz

Submission #872049

# Submission time Handle Problem Language Result Execution time Memory
872049 2023-11-12T07:55:37 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
64.1392 / 100
 459 ms 26568 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define len(x) (int) x.size()
#define pb push_back
mt19937 rnd(time(0));

const int N = 1e5 + 7, LG = 19;
int n, q, rt, place[N], h[N], mn[N], par[LG][N];
int seg[N << 2], lazy[N << 2];
vector<int> adj[N], ord;

void read_input() {
	cin >> n >> q;
	for (int i = 0; i < n; i++) {
		int par;
		cin >> par;
		if (!par) 
			rt = i;
		else 
			adj[--par].pb(i);
	}
}

int k_par(int u, int k) {
	for (int i = 0; i < LG; i++)
		if ((k >> i) & 1)
			u = par[i][u];
	return u;
}

void dfs_mn(int u) {
	mn[u] = u;
	for (int v: adj[u]) {
		par[0][v] = u;
		h[v] = 1 + h[u];
		dfs_mn(v);
		mn[u] = min(mn[u], mn[v]);
	}
	sort(all(adj[u]), [] (int i, int j) {
			return mn[i] < mn[j];
			});
}

void dfs_ord(int u) {
	for (int v: adj[u])
		dfs_ord(v);
	ord.pb(u);
}

void shift(int id, int st, int mid, int en) {
	if (!lazy[id])
		return;
	int lc = id << 1, rc = lc | 1;
	seg[lc] = mid - st, lazy[lc] = true;
	seg[rc] = mid - en, lazy[rc] = true;
	lazy[id] = 0;
}

void upd(int l, int r, bool b, int id = 1, int st = 0, int en = n) {
	if (r <= st || l >= en)
		return;
	if (st >= l && en <= r) {
		if (b) {
			seg[id] = en - st;
			lazy[id] = true;
		}
		else
			seg[id] = 0;
		return;
	}
	int mid = (st + en) >> 1, lc = id << 1, rc = lc | 1;
	shift(id, st, mid, en);
	upd(l, r, b, lc, st, mid), upd(l, r, b, rc, mid, en);
	seg[id] = seg[lc] + seg[rc];
}

int get(int p, int id = 1, int st = 0, int en = n) {
	if (en - st == 1)
		return seg[id];
	int mid = (st + en) >> 1, lc = id << 1, rc = lc | 1;
	shift(id, st, mid, en);
	if (p < mid)
		return get(p, lc, st, mid);
	return get(p, rc, mid, en);
}

int find_k(int k, int id = 1, int st = 0, int en = n) {
	if (en - st == 1)
		return st;
	int lc = id << 1, rc = lc | 1;
	int mid = (st + en) >> 1;
	shift(id, st, mid, en);
	if (mid - st - seg[lc] >= k)
		return find_k(k, lc, st, mid);
	return find_k(k - (mid - st - seg[lc]), rc, mid, en);
}

void solve() {
	dfs_mn(rt);
	dfs_ord(rt);
	for (int i = 0; i < n; i++)
		place[ord[i]] = i;
	par[0][rt] = rt;
	for (int i = 1; i < LG; i++)
		for (int j = 0; j < n; j++)
			par[i][j] = par[i - 1][par[i - 1][j]];
	while (q--) {
		int type;
		cin >> type;
		if (type == 1) {
			int k;
			cin >> k;
			int t = find_k(k);
			upd(0, t + 1, 1);
			cout << ord[t] + 1 << '\n';
		}
		else {
			int u;
			cin >> u;
			u--;
			upd(place[u], place[u] + 1, 0);
			if (!get(place[par[0][u]])) {
				cout << 0 << '\n';
				continue;
			}
			int l = 1, r = h[u] + 1;
			while (r - l > 1) {
				int mid = (l + r) / 2;
				if (get(place[k_par(u, mid)]))
					l = mid;
				else
					r = mid;
			}
			int v = k_par(u, l);
			upd(place[v], place[v] + 1, 0);
			upd(place[u], place[u] + 1, 1);
			cout << h[u] - h[v] << '\n';
		}
	}
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), solve();
	return 0;
}

Subtask #1
9.61538461538 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 12888 KB Output isn't correct
2 Correct 88 ms 15468 KB Output is correct
3 Correct 42 ms 15576 KB Output is correct
4 Incorrect 2 ms 12888 KB Output isn't correct
5 Incorrect 2 ms 12892 KB Output isn't correct
6 Correct 2 ms 12892 KB Output is correct
7 Incorrect 2 ms 12892 KB Output isn't correct
8 Correct 2 ms 12892 KB Output is correct
9 Incorrect 7 ms 12892 KB Output isn't correct
10 Incorrect 17 ms 13648 KB Output isn't correct
11 Incorrect 84 ms 15564 KB Output isn't correct
12 Correct 39 ms 15564 KB Output is correct
13 Incorrect 64 ms 15532 KB Output isn't correct

Subtask #2
12.8571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 15688 KB Output is correct
2 Incorrect 66 ms 21332 KB Output isn't correct
3 Correct 46 ms 16596 KB Output is correct
4 Incorrect 37 ms 15700 KB Output isn't correct
5 Incorrect 38 ms 15460 KB Output isn't correct
6 Incorrect 39 ms 15448 KB Output isn't correct
7 Incorrect 37 ms 14684 KB Output isn't correct
8 Correct 27 ms 15520 KB Output is correct
9 Correct 68 ms 21428 KB Output is correct
10 Incorrect 73 ms 21008 KB Output isn't correct
11 Incorrect 59 ms 20944 KB Output isn't correct
12 Incorrect 61 ms 18892 KB Output isn't correct
13 Correct 52 ms 24780 KB Output is correct
14 Correct 50 ms 16588 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 17364 KB Output is correct
2 Correct 217 ms 19168 KB Output is correct
3 Correct 222 ms 23504 KB Output is correct
4 Correct 154 ms 19896 KB Output is correct
5 Correct 163 ms 19412 KB Output is correct
6 Correct 135 ms 19408 KB Output is correct
7 Correct 143 ms 17872 KB Output is correct
8 Correct 225 ms 23740 KB Output is correct
9 Correct 224 ms 21708 KB Output is correct
10 Correct 245 ms 21456 KB Output is correct
11 Correct 228 ms 21272 KB Output is correct
12 Correct 211 ms 19300 KB Output is correct
13 Correct 459 ms 26568 KB Output is correct
14 Correct 73 ms 16596 KB Output is correct

Subtask #4
1.66666666667 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 336 ms 21644 KB Output isn't correct
2 Incorrect 257 ms 19144 KB Output isn't correct
3 Correct 64 ms 26404 KB Output is correct
4 Incorrect 336 ms 21716 KB Output isn't correct
5 Incorrect 247 ms 21276 KB Output isn't correct
6 Incorrect 94 ms 20968 KB Output isn't correct
7 Incorrect 249 ms 19288 KB Output isn't correct
8 Correct 64 ms 26320 KB Output is correct
9 Correct 46 ms 16592 KB Output is correct