Submission #481413

#	Time	Username	Problem	Language	Result	Execution time	Memory
481413		rainboy	Klasika (COCI20_klasika)	C11	110 / 110	3440 ms	123604 KiB

klasika

#include <stdio.h>
#include <stdlib.h>

#define N	200001
#define H	30
#define N_	(1 + N * H)
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }

unsigned int X = 12345;

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

int *ej[N], eo[N];

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

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

int ta[N], tb[N];

void dfs(int i) {
	static int time;
	int o;

	ta[i] = time++;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs(j);
	}
	tb[i] = time;
}

int zz[1 + N_], ll[1 + N_], rr[1 + N_], kk[1 + N_], u_, l_, r_;

int node(int k) {
	static int _ = 1;

	zz[_] = rand_();
	kk[_] = k;
	return _++;
}

void split(int u, int k) {
	if (u == 0) {
		u_ = l_ = r_ = 0;
		return;
	}
	if (kk[u] < k) {
		split(rr[u], k);
		rr[u] = l_, l_ = u;
	} else {
		split(ll[u], k);
		ll[u] = r_, r_ = u;
	}
}

int merge(int u, int v) {
	if (u == 0)
		return v;
	if (v == 0)
		return u;
	if (zz[u] < zz[v]) {
		rr[u] = merge(rr[u], v);
		return u;
	} else {
		ll[v] = merge(u, ll[v]);
		return v;
	}
}

int tr_add(int u, int k) {
	split(u, k);
	return merge(merge(l_, node(k)), r_);
}

int tr_ceil(int u, int k) {
	int k_ = INF;

	while (u)
		if (kk[u] >= k)
			k_ = kk[u], u = ll[u];
		else
			u = rr[u];
	return k_;
}

int tt[N_][2], tr[N_], _ = 2;

void update(int a, int x) {
	int h, t;

	for (h = H - 1, t = 1; h >= 0; h--) {
		int c = a >> h & 1;

		if (!tt[t][c])
			tt[t][c] = _++;
		t = tt[t][c];
		tr[t] = tr_add(tr[t], x);
	}
}

int query(int a, int l, int r) {
	int h, t, x;

	x = 0;
	for (h = H - 1, t = 1; h >= 0; h--) {
		int c = (a >> h & 1) ^ 1;

		if (tt[t][c] && tr_ceil(tr[tt[t][c]], l) < r)
			x |= 1 << h;
		else
			c ^= 1;
		t = tt[t][c];
	}
	return x;
}

int main() {
	static int aa[N], ii[N], jj[N];
	int n, q, h;

	scanf("%d", &q);
	n = 1;
	for (h = 0; h < q; h++) {
		static char s[8];
		int i, j;

		scanf("%s%d", s, &i), i--;
		if (s[0] == 'A') {
			j = n++;
			scanf("%d", &aa[j]), aa[j] ^= aa[i];
			append(i, j);
			ii[h] = -1, jj[h] = j;
		} else {
			scanf("%d", &j), j--;
			ii[h] = i, jj[h] = j;
		}
	}
	dfs(0);
	update(aa[0], 0);
	for (h = 0; h < q; h++)
		if (ii[h] == -1)
			update(aa[jj[h]], ta[jj[h]]);
		else
			printf("%d\n", query(aa[ii[h]], ta[jj[h]], tb[jj[h]]));
	return 0;
}

Compilation message (stderr)

klasika.c: In function 'append':
klasika.c:22:33: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  if (o == 0 || o >= 2 && (o & o - 1) == 0)
      |                               ~~^~~
klasika.c:22:23: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   22 |  if (o == 0 || o >= 2 && (o & o - 1) == 0)
      |                ~~~~~~~^~~~~~~~~~~~~~~~~~~
klasika.c: In function 'main':
klasika.c:131:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |  scanf("%d", &q);
      |  ^~~~~~~~~~~~~~~
klasika.c:137:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |   scanf("%s%d", s, &i), i--;
      |   ^~~~~~~~~~~~~~~~~~~~
klasika.c:140:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |    scanf("%d", &aa[j]), aa[j] ^= aa[i];
      |    ^~~~~~~~~~~~~~~~~~~
klasika.c:144:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |    scanf("%d", &j), j--;
      |    ^~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 22 / 22
• Subtask 3: 33 / 33
• Subtask 4: 44 / 44