Submission #848840

#	Time	Username	Problem	Language	Result	Execution time	Memory
848840		rainboy	Beech Tree (IOI23_beechtree)	C++17	22 / 100	58 ms	18900 KiB

beechtree

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

using namespace std;

typedef vector<int> vi;

const int N = 200000, M = 200000;

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

unsigned int X = 12345;

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

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

char used[M];

int duplicate(int i) {
	int dup = 0;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (used[cc[j]])
			dup = 1;
		used[cc[j]] = 1;
	}
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		used[cc[j]] = 0;
	}
	return dup;
}

int contains(int i1, int i2) {
	for (int o = eo[i1]; o--; ) {
		int j = ej[i1][o];
		used[cc[j]] = 1;
	}
	int cont = 1;
	for (int o = eo[i2]; o--; ) {
		int j = ej[i2][o];
		if (!used[cc[j]])
			cont = 0;
	}
	for (int o = eo[i1]; o--; ) {
		int j = ej[i1][o];
		used[cc[j]] = 0;
	}
	return cont;
}

int sz[N], qu[N], ta[N], tb[N];

void dfs(int i) {
	static int time;
	sz[i] = 1, qu[ta[i] = time++] = i;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		dfs(j);
		sz[i] += sz[j];
	}
	tb[i] = time;
}

int compare_sz(int i, int j) {
	while (i != -1 && j != -1) {
		if (sz[i] != sz[j])
			return sz[j] - sz[i];
		i = pp[i], j = pp[j];
	}
	return ta[i] - ta[j];
}

int compare_eo(int i, int j) { return eo[i] - eo[j]; }

int (*compare)(int, int);

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) {
			int c = compare(ii[j], i_);
			if (c == 0)
				j++;
			else if (c < 0) {
				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 qu_[N], kk[M];
int hh[N];

vi beechtree(int n, int m, vi pp_, vi cc_) {
	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);
	int line = 1;
	for (int i = 1; i < n; i++)
		if (pp[i] != i - 1) {
			line = 0;
			break;
		}
	vi ans(n, 0);
	if (line) {
		ans[n - 1] = 1;
		for (int i = n - 2; i >= 0 && cc[i + 1] == cc[n - 1]; i--)
			ans[i] = 1;
	} else if (n <= 200) {
		dfs(0);
		for (int i = 0; i < n; i++) {
			for (int h = ta[i]; h < tb[i]; h++)
				qu_[h - ta[i]] = qu[h];
			compare = compare_sz, sort(qu_, 0, tb[i] - ta[i]);
			ans[i] = 1;
			for (int h = 1; h < tb[i] - ta[i]; h++) {
				int j = qu_[h];
				if (qu_[kk[cc[j]]++] != pp[j]) {
					ans[i] = 0;
					break;
				}
			}
			for (int h = 1; h < tb[i] - ta[i]; h++) {
				int j = qu_[h];
				kk[cc[j]] = 0;
			}
		}
	} else
		for (int i = n - 1; i >= 0; i--) {
			hh[i] = 0;
			for (int o = 0; o < eo[i]; o++)
				hh[i] = max(hh[i], hh[ej[i][o]] + 1);
			if (hh[i] > 2) {
				ans[i] = 0;
				continue;
			}
			compare = compare_eo, sort(ej[i], 0, eo[i]);
			ans[i] = !duplicate(i);
			for (int o = 0; o < eo[i]; o++)
				if (duplicate(ej[i][o])) {
					ans[i] = 0;
					break;
				}
			for (int o = 0; o < eo[i]; o++)
				if (!contains(o + 1 == eo[i] ? i : ej[i][o + 1], ej[i][o])) {
					ans[i] = 0;
					break;
				}
		}
	return ans;
}

Compilation message (stderr)

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

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