Submission #850119

#	Time	Username	Problem	Language	Result	Execution time	Memory
850119		rainboy	Beech Tree (IOI23_beechtree)	C++17	100 / 100	227 ms	108960 KiB

beechtree

/* https://oj.uz/submission/841403 (model_code) */
#include "beechtree.h"
#include <cstdlib>
#include <vector>

using namespace std;

typedef vector<int> vi;

const int N = 200000, M = 200000, LN = 18, N_ = N * (LN + 1) + 1, MD = 0x7fffffff, X = 123456789;	/* LN = ceil(log2(N)) */

int n;

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

int min_(int i, int j) { return sz[i] < sz[j] ? i : j; }
int max_(int i, int j) { return sz[i] > sz[j] ? i : j; }

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;
}

long long *ek[M]; int *ev[M], eo_[M];

int hash_(long long k) {
	return (k / MD * X + k % MD) % MD * X % MD % M;
}

int add(long long k, int v) {
	int h = hash_(k);
	for (int o = eo_[h]; o--; )
		if (ek[h][o] == k)
			return 0;
	int o = eo_[h]++;
	if (o >= 2 && (o & o - 1) == 0) {
		ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
		ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
	}
	ek[h][o] = k, ev[h][o] = v;
	return 1;
}

int get(long long k) {
	int h = hash_(k);
	for (int o = eo_[h]; o--; )
		if (ek[h][o] == k)
			return ev[h][o];
	return -1;
}

int contained(int i1, int i2) {
	for (int o = eo[i1]; o--; ) {
		int j1 = ej[i1][o], j2 = get((long long) i2 * M + cc[j1]);
		if (j2 == -1 || sz[j1] > sz[j2])
			return 0;
	}
	return 1;
}

int ll[N_], rr[N_], mn[N_], mx[N_];

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

int incr, i_, type;

int merge(int t1, int t2, int l, int r) {
	if (t1 == 0 && t2 == 0)
		return 0;
	if (t1 == 0) {
		if (i_ != -1 && type != 1 && !contained(i_, mn[t2]))
			incr = 0;
		i_ = mx[t2], type = 1;
		return t2;
	}
	if (t2 == 0) {
		if (i_ != -1 && type != 2 && !contained(i_, mn[t1]))
			incr = 0;
		i_ = mx[t1], type = 2;
		return t1;
	}
	if (r - l == 1) {
		if (!contained(mn[t1], mn[t2]))
			incr = 0;
		i_ = mx[t1], type = 1;
		return t1;
	}
	int m = (l + r) / 2;
	ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
	mn[t1] = min_(mn[t1], mn[t2]), mx[t1] = max_(mx[t1], mx[t2]);
	return t1;
}

vi good; int tt[N];

void dfs(int i) {
	sz[i] = 1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs(j);
		sz[i] += sz[j];
	}
	if (!good[i])
		return;
	tt[i] = node(0, n, sz[i] - 1, i);
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (!good[j]) {
			good[i] = 0;
			return;
		}
		incr = 1, i_ = -1, type = -1, tt[i] = merge(tt[i], tt[j], 0, n);
		if (!incr) {
			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);
	good.clear(); good.resize(n, 1);
	for (int h = 0; h < M; h++) {
		ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
		ev[h] = (int *) malloc(2 * sizeof *ev[h]);
	}
	for (int i = 1; i < n; i++)
		if (!add((long long) pp[i] * M + cc[i], i))
			good[pp[i]] = 0;
	dfs(0);
	return good;
}

Compilation message (stderr)

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

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