Submission #443437

#	Time	Username	Problem	Language	Result	Execution time	Memory
443437		rainboy	Split the Attractions (IOI19_split)	C++14	7 / 100	672 ms	1048580 KiB

split

#include "split.h"
#include <stdlib.h>

using namespace std;

typedef vector<int> vi;

const int N = 100000;

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 sz[N], pp[N];

void dfs1(int p, int i) {
	int o;

	pp[i] = p, sz[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j);
			sz[i] += sz[j];
		}
	}
}

vi xx;
int k;

void dfs2(int p, int i, int x) {
	int o;

	if (k == 0)
		return;
	k--;
	xx[i] = x;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs2(i, j, x);
	}
}

vi find_split(int n, int a, int b, int c, vi ii, vi jj) {
	int h, i, x, y;

	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++)
		append(ii[h], jj[h]), append(jj[h], ii[h]);
	if (a > c && b > c)
		x = 1, y = 2;
	else if (a > b && c > b)
		b = c, x = 1, y = 3;
	else
		a = c, x = 3, y = 2;
	dfs1(-1, 0);
	xx.resize(n);
	for (i = 0; i < n; i++) {
		if (sz[i] >= a && n - sz[i] >= b) {
			k = a, dfs2(pp[i], i, x);
			k = b, dfs2(i, pp[i], y);
			for (i = 0; i < n; i++)
				if (xx[i] == 0)
					xx[i] = x ^ y;
			break;
		}
		if (sz[i] >= b && n - sz[i] >= a) {
			k = b, dfs2(pp[i], i, y);
			k = a, dfs2(i, pp[i], x);
			for (i = 0; i < n; i++)
				if (xx[i] == 0)
					xx[i] = x ^ y;
			break;
		}
	}
	return xx;
}

Compilation message (stderr)

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

• Subtask 1: 7 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 22
• Subtask 4: 0 / 24
• Subtask 5: 0 / 36