Submission #848833

#	Time	Username	Problem	Language	Result	Execution time	Memory
848833		rainboy	Beech Tree (IOI23_beechtree)	C++17	22 / 100	70 ms	15632 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 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;
}

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 (eo[ii[j]] == eo[i_])
				j++;
			else if (eo[ii[j]] < eo[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;
	}
}

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 hh[N];

vi beechtree(int n, int m, vi pp, vi cc_) {
	for (int i = 1; i < n; 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
		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;
			}
			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: 0 / 9
• Subtask 2: 5 / 5
• Subtask 3: 9 / 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