oj.uz

답안 #872053

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
872053 2023-11-12T07:59:23 Z vjudge1 Ball Machine (BOI13_ballmachine) C++17
100 / 100
 390 ms 26480 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] = en - mid, 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
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 12892 KB Output is correct
2 Correct 98 ms 15476 KB Output is correct
3 Correct 52 ms 15840 KB Output is correct
4 Correct 2 ms 12888 KB Output is correct
5 Correct 3 ms 13040 KB Output is correct
6 Correct 2 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12996 KB Output is correct
9 Correct 8 ms 13148 KB Output is correct
10 Correct 20 ms 13640 KB Output is correct
11 Correct 91 ms 15568 KB Output is correct
12 Correct 39 ms 15568 KB Output is correct
13 Correct 107 ms 15736 KB Output is correct

Subtask #2
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 15544 KB Output is correct
2 Correct 69 ms 21044 KB Output is correct
3 Correct 46 ms 16596 KB Output is correct
4 Correct 40 ms 15704 KB Output is correct
5 Correct 39 ms 15464 KB Output is correct
6 Correct 38 ms 15448 KB Output is correct
7 Correct 37 ms 14792 KB Output is correct
8 Correct 28 ms 15708 KB Output is correct
9 Correct 68 ms 21500 KB Output is correct
10 Correct 68 ms 21192 KB Output is correct
11 Correct 67 ms 21532 KB Output is correct
12 Correct 63 ms 18892 KB Output is correct
13 Correct 51 ms 24780 KB Output is correct
14 Correct 47 ms 16632 KB Output is correct

Subtask #3
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 99 ms 17328 KB Output is correct
2 Correct 233 ms 19192 KB Output is correct
3 Correct 257 ms 23708 KB Output is correct
4 Correct 175 ms 20020 KB Output is correct
5 Correct 147 ms 19416 KB Output is correct
6 Correct 134 ms 19412 KB Output is correct
7 Correct 127 ms 17924 KB Output is correct
8 Correct 271 ms 23808 KB Output is correct
9 Correct 227 ms 21612 KB Output is correct
10 Correct 287 ms 21284 KB Output is correct
11 Correct 255 ms 21196 KB Output is correct
12 Correct 223 ms 19192 KB Output is correct
13 Correct 390 ms 26480 KB Output is correct
14 Correct 100 ms 16608 KB Output is correct

Subtask #4
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 354 ms 22064 KB Output is correct
2 Correct 241 ms 19144 KB Output is correct
3 Correct 70 ms 26328 KB Output is correct
4 Correct 362 ms 22000 KB Output is correct
5 Correct 247 ms 21200 KB Output is correct
6 Correct 234 ms 21460 KB Output is correct
7 Correct 248 ms 19248 KB Output is correct
8 Correct 56 ms 26224 KB Output is correct
9 Correct 47 ms 16512 KB Output is correct