Submission #848991

#	Time	Username	Problem	Language	Result	Execution time	Memory
848991		rainboy	Beech Tree (IOI23_beechtree)	C++17	0 / 100	3 ms	24924 KiB

beechtree

#include "beechtree.h"
#include <cstdlib>
#include <cstring>

using namespace std;

typedef vector<int> vi;

const int N = 200000, LN = 18, N_ = N * (LN + 1) + 1;	/* LN = ceil(log2(N)) */

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

unsigned int X = 12345;

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

int n;
int pp[N], cc[N];
int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

int xx[N], ta[N], tb[N];

void dfs1(int i) {
	static int time;
	ta[i] = time++;
	xx[i] = 1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs1(j);
		xx[i] += xx[j];
	}
	tb[i] = time;
}

int qq[N], yy[N], ii[N], jj[N], kk[N + 2];

void extend() {
	for (int i = n - 1; i >= 0; i--) {
		yy[i] = qq[i] == -1 ? 0 : xx[qq[i]];
		qq[i] = qq[i] == -1 ? -1 : qq[qq[i]];
	}
}

void sort(int *xx, int *ii, int *jj) {
	memset(kk, 0, (n + 2) * sizeof *kk);
	for (int i = 0; i < n; i++) {
		int j = ii[i];
		kk[xx[j] + 1]++;
	}
	for (int x = 1; x <= n + 1; x++)
		kk[x] += kk[x - 1];
	for (int i = 0; i < n; i++) {
		int j = ii[i];
		jj[kk[xx[j]]++] = j;
	}
}

void compress() {
	for (int i = 0, x = 0; i < n; i++)
		xx[ii[i]] = i + 1 == n || xx[ii[i + 1]] != xx[ii[i]] || yy[ii[i + 1]] != yy[ii[i]] ? x++ : x;
}

int ll[N_], rr[N_], kk_[N_];

int node(int l, int r, int x) {
	static int _ = 1;
	int t_ = _++;
	kk_[t_] = 1;
	if (r - l > 1) {
		int m = (l + r) / 2;
		if (x < m)
			ll[t_] = node(l, m, x);
		else
			rr[t_] = node(m, r, x);
	}
	return t_;
}

int merge(int t1, int t2) {
	if (t1 == 0)
		return t2;
	if (t2 == 0)
		return t1;
	ll[t1] = merge(ll[t1], ll[t2]), rr[t1] = merge(rr[t1], rr[t2]), kk_[t1] += kk_[t2];
	return t1;
}

int query(int t, int l, int r, int k) {
	if (r - l == 1)
		return l;
	int m = (l + r) / 2;
	return k <= kk_[ll[t]] ? query(ll[t], l, m, k) : query(rr[t], m, r, k - kk_[ll[t]]);
}

int ll_[N_], rr_[N_], mn[N_], mx[N_];

int node_(int l, int r, int x) {
	static int _ = 1;
	int t_ = _++;
	mn[t_] = mx[t_] = xx[pp[ii[x]]];
	if (r - l > 1) {
		int m = (l + r) / 2;
		if (x < m)
			ll_[t_] = node_(l, m, x);
		else
			rr_[t_] = node_(m, r, x);
	}
	return t_;
}

int x_, incr;

int merge_(int t1, int t2) {
	if (t1 == 0 && t2 == 0)
		return 0;
	if (t1 == 0) {
		if (x_ > mn[t2])
			incr = 0;
		x_ = mx[t2];
		return t2;
	}
	if (t2 == 0) {
		if (x_ > mn[t1])
			incr = 0;
		x_ = mx[t1];
		return t1;
	}
	ll_[t1] = merge_(ll_[t1], ll_[t2]), rr_[t1] = merge_(rr_[t1], rr_[t2]);
	mn[t1] = min(mn[t1], mn[t2]), mx[t1] = max(mx[t1], mx[t2]);
	return t1;
}

int tt[N], tt_[N]; char good[N];

void dfs2(int i) {
	good[i] = 1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs2(j);
		if (!good[j])
			good[i] = 0;
	}
	if (!good[i])
		return;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		jj[cc[j]] = -1;
	}
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (jj[cc[j]] != -1) {
			good[i] = 0;
			return;
		}
		jj[cc[j]] = j;
	}
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		tt_[j] = node_(0, n, xx[j]), yy[j] = xx[i], kk[j] = 1;
	}
	tt[i] = node(0, n, xx[i]);
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		tt[i] = merge(tt[i], tt[j]);
		for (int o = eo[j]; o--; ) {
			int k = ej[j][o], j_ = jj[cc[k]];
			if (j_ == -1) {
				good[i] = 0;
				return;
			}
			x_ = -1, incr = 1, tt_[j_] = merge_(tt_[j_], tt_[k]);
			if (!incr) {
				good[i] = 0;
				return;
			}
			yy[j_] = max(yy[j_], yy[k]), kk[j_] += kk[k];
		}
	}
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (yy[j] > query(tt[i], 0, n, kk[j])) {
			good[i] = 0;
			return;
		}
	}
}

vi beechtree(int n_, int m, vi pp_, vi cc_) {
	n = n_;
	for (int i = 0; i < n; i++)
		pp[i] = pp_[i], cc[i] = cc_[i] - 1;
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int i = 1; i < n; i++)
		append(pp[i], i);
	dfs1(0);
	for (int i = 0; i < n; i++) {
		xx[i] = n - xx[i];
		qq[i] = pp[i];
		ii[i] = i;
	}
	for (int l = 0; l <= LN; l++) {
		extend();
		sort(yy, ii, jj);
		sort(xx, jj, ii);
		compress();
	}
	for (int i = 0; i < n; i++)
		yy[i] = ta[i];
	sort(yy, ii, jj);
	sort(xx, jj, ii);
	compress();
	memset(jj, -1, m * sizeof *jj);
	dfs2(0);
	vi good_(n, 0);
	for (int i = 0; i < n; i++)
		good_[i] = good[i];
	return good_;
}

Compilation message (stderr)

beechtree.cpp: In function 'void append(int, int)':
beechtree.cpp:26:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   26 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 9
• Subtask 2: 0 / 5
• Subtask 3: 0 / 9
• Subtask 4: 0 / 8
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 12
• Subtask 8: 0 / 17
• Subtask 9: 0 / 12