oj.uz

Submission #544604

# Submission time Handle Problem Language Result Execution time Memory
544604 2022-04-02T13:30:47 Z rainboy Ball Machine (BOI13_ballmachine) C
100 / 100
 119 ms 18388 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define N	100000
#define N_	(1 << 17)	/* N_ = pow2(ceil(log2(N))) */

unsigned int X = 12345;

int rand_() {
	return (X *= 3) >> 1;
}

int min(int a, int b) { return a < b ? a : b; }

int *oj[N], oo[N];

void append(int i, int j) {
	int o = oo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		oj[i] = (int *) realloc(oj[i], o * 2 * sizeof *oj[i]);
	oj[i][o] = j;
}

int pp[N], qq[N], dd[N], sz[N], jj[N], dp[N], qu[N], cnt;

void dfs1(int i, int d) {
	int o, j_;

	qu[cnt++] = i;
	j_ = -1;
	dd[i] = d, sz[i] = 1, dp[i] = i;
	for (o = 0; o < oo[i]; o++) {
		int j = oj[i][o];

		dfs1(j, d + 1);
		if (j_ == -1 || sz[j_] < sz[j])
			j_ = j;
		sz[i] += sz[j];
		dp[i] = min(dp[i], dp[j]);
	}
	jj[i] = j_;
	if (j_ != -1)
		qq[j_] = -1;
}

int lca_(int i, int j) {
	int i_ = i, a;

	while (qq[i] != qq[j])
		if (dd[qq[i]] > dd[qq[j]])
			i = pp[qq[i]];
		else
			j = pp[qq[j]];
	a = dd[i] < dd[j] ? i : j;
	i = qq[i_];
	while (dd[i] > dd[a] + 1)
		i = qq[pp[i]];
	return dd[i] == dd[a] + 1 ? i : jj[a];
}

void sort(int *ii, int l, int r) {
	while (l < r) {
		int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;

		while (j < k)
			if (dp[ii[j]] == dp[i_])
				j++;
			else if (dp[ii[j]] < dp[i_]) {
				tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
				i++, j++;
			} else {
				k--;
				tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
			}
		sort(ii, l, i);
		l = k;
	}
}

int hh[N];

void dfs2(int i) {
	int o;

	sort(oj[i], 0, oo[i]);
	for (o = 0; o < oo[i]; o++) {
		int j = oj[i][o];

		dfs2(j);
	}
	hh[qu[cnt] = i] = cnt, cnt++;
}

int st[N_ * 2], h_, n_; char lz[N_];

void put(int i) {
	st[i] = 0;
	if (i < n_)
		lz[i] = 1;
}

void pus(int i) {
	if (lz[i]) {
		put(i << 1), put(i << 1 | 1);
		lz[i] = 0;
	}
}

void pul(int i) {
	if (!lz[i])
		st[i] = st[i << 1] + st[i << 1 | 1];
}

void push(int i) {
	int h;

	for (h = h_; h > 0; h--)
		pus(i >> h);
}

void pull(int i) {
	while (i > 1)
		pul(i >>= 1);
}

void build(int n) {
	int i;

	h_ = 0;
	while (1 << h_ < n)
		h_++;
	n_ = 1 << h_;
	for (i = 0; i < n; i++)
		st[n_ + i] = 1;
	for (i = n_ - 1; i > 0; i--)
		pul(i);
}

int find(int k) {
	int i = 1;

	while (i < n_) {
		pus(i);
		i <<= 1;
		if (k > st[i])
			k -= st[i], i ^= 1;
	}
	return i - n_;
}

void update(int r) {
	int l = 0, l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1) {
		if ((l & 1) == 1)
			put(l++);
		if ((r & 1) == 0)
			put(r--);
	}
	pull(l_), pull(r_);
}

void upd(int i) {
	push(i += n_);
	st[i] = 1;
	pull(i);
}

int higher(int l) {
	int r = n_ - 1, l_ = l += n_, r_ = r += n_;

	push(l_), push(r_);
	for ( ; l <= r; l >>= 1, r >>= 1)
		if ((l & 1) == 1) {
			if (st[l] > 0) {
				while (l < n_) {
					pus(l);
					l = st[l << 1] > 0 ? l << 1 : l << 1 | 1;
				}
				return l - n_;
			}
			l++;
		}
	return -1;
}

int main() {
	int n, q, h, i, r;

	scanf("%d%d", &n, &q);
	r = -1;
	for (i = 0; i < n; i++)
		oj[i] = (int *) malloc(2 * sizeof *oj[i]);
	for (i = 0; i < n; i++) {
		scanf("%d", &pp[i]), pp[i]--;
		if (pp[i] == -1)
			r = i;
		else
			append(pp[i], i);
	}
	dfs1(r, 0);
	for (h = 0; h < cnt; h++) {
		i = qu[h];
		qq[i] = qq[i] ? qq[pp[i]] : i;
	}
	cnt = 0;
	dfs2(r);
	build(n);
	while (q--) {
		int t;

		scanf("%d", &t);
		if (t == 1) {
			int k;

			scanf("%d", &k);
			h = find(k);
			update(h);
			printf("%d\n", qu[h] + 1);
		} else {
			int p;

			scanf("%d", &i), i--;
			h = higher(hh[i]);
			p = h == -1 ? r : lca_(i, qu[h]);
			upd(hh[p]);
			printf("%d\n", dd[i] - dd[p]);
		}
	}
	return 0;
}

Compilation message

ballmachine.c: In function 'append':
ballmachine.c:21:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   21 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
ballmachine.c: In function 'main':
ballmachine.c:193:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  193 |  scanf("%d%d", &n, &q);
      |  ^~~~~~~~~~~~~~~~~~~~~
ballmachine.c:198:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |   scanf("%d", &pp[i]), pp[i]--;
      |   ^~~~~~~~~~~~~~~~~~~
ballmachine.c:215:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  215 |   scanf("%d", &t);
      |   ^~~~~~~~~~~~~~~
ballmachine.c:219:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |    scanf("%d", &k);
      |    ^~~~~~~~~~~~~~~
ballmachine.c:226:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  226 |    scanf("%d", &i), i--;
      |    ^~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 73 ms 6988 KB Output is correct
3 Correct 60 ms 6940 KB Output is correct
4 Correct 1 ms 292 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 432 KB Output is correct
8 Correct 1 ms 436 KB Output is correct
9 Correct 5 ms 700 KB Output is correct
10 Correct 13 ms 1972 KB Output is correct
11 Correct 63 ms 7104 KB Output is correct
12 Correct 64 ms 7068 KB Output is correct
13 Correct 67 ms 7060 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 4072 KB Output is correct
2 Correct 91 ms 14180 KB Output is correct
3 Correct 78 ms 10068 KB Output is correct
4 Correct 42 ms 4876 KB Output is correct
5 Correct 45 ms 4884 KB Output is correct
6 Correct 42 ms 4808 KB Output is correct
7 Correct 41 ms 3992 KB Output is correct
8 Correct 39 ms 4044 KB Output is correct
9 Correct 83 ms 14176 KB Output is correct
10 Correct 86 ms 14048 KB Output is correct
11 Correct 84 ms 14064 KB Output is correct
12 Correct 80 ms 11968 KB Output is correct
13 Correct 82 ms 16084 KB Output is correct
14 Correct 75 ms 10056 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7376 KB Output is correct
2 Correct 91 ms 12364 KB Output is correct
3 Correct 72 ms 14608 KB Output is correct
4 Correct 59 ms 11476 KB Output is correct
5 Correct 61 ms 11392 KB Output is correct
6 Correct 59 ms 11340 KB Output is correct
7 Correct 58 ms 9768 KB Output is correct
8 Correct 63 ms 14656 KB Output is correct
9 Correct 91 ms 14332 KB Output is correct
10 Correct 91 ms 14248 KB Output is correct
11 Correct 103 ms 14244 KB Output is correct
12 Correct 95 ms 12364 KB Output is correct
13 Correct 96 ms 18388 KB Output is correct
14 Correct 83 ms 10660 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 14476 KB Output is correct
2 Correct 96 ms 12344 KB Output is correct
3 Correct 93 ms 17984 KB Output is correct
4 Correct 91 ms 14432 KB Output is correct
5 Correct 119 ms 14292 KB Output is correct
6 Correct 93 ms 14204 KB Output is correct
7 Correct 94 ms 12444 KB Output is correct
8 Correct 84 ms 17996 KB Output is correct
9 Correct 76 ms 10016 KB Output is correct