Submission #443735

#	Time	Username	Problem	Language	Result	Execution time	Memory
443735		rainboy	Split the Attractions (IOI19_split)	C++14	100 / 100	141 ms	16804 KiB

split

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

using namespace std;

typedef vector<int> vi;

const int N = 100000;

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

int *ej[N], eo[N], 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 pp[N], sz[N], ta[N], tb[N], i_;
int a, b, x, y, z;

void dfs1(int p, int i) {
	static int time;
	int o, centroid;

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

		if (!ta[j]) {
			dfs1(i, j);
			if (sz[j] * 2 > n)
				centroid = 0;
			sz[i] += sz[j];
			tb[i] = min(tb[i], tb[j]);
		} else if (j != p)
			tb[i] = min(tb[i], ta[j]);
	}
	if ((n - sz[i]) * 2 > n)
		centroid = 0;
	if (centroid)
		i_ = i;
}

vi xx; int k;

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

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

		if (j != p && (!strict || pp[j] == i || pp[i] == j))
			dfs2(i, j, x, strict);
	}
}

vi find_split(int n_, int a_, int b_, int c, vi ii, vi jj) {
	int m = ii.size(), h, i, j, o, tmp;

	n = n_;
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++)
		append(ii[h], jj[h]), append(jj[h], ii[h]);
	a = a_, b = b_;
	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;
	if (a > b)
		tmp = a, a = b, b = tmp, tmp = x, x = y, y = tmp;
	z = x ^ y;
	dfs1(-1, 0), i = i_;
	if (pp[i] != -1)
		sz[pp[i]] = n - sz[i];
	xx.resize(n);
	for (o = eo[i]; o--; ) {
		j = ej[i][o];
		if ((j == pp[i] || pp[j] == i) && sz[j] >= a) {
			k = a, dfs2(i, j, x, 1);
			k = b, dfs2(j, i, y, 1);
			return xx;
		}
	}
	k = sz[pp[i]];
	for (o = eo[i]; o--; ) {
		j = ej[i][o];
		if (pp[j] == i && tb[j] < ta[i] && (k += sz[j]) >= a) {
			if (k * 2 >= n)
				tmp = a, a = b, b = tmp, tmp = x, x = y, y = tmp;
			k = b - 1, xx[i] = y;
			while (o--) {
				j = ej[i][o];
				if (pp[j] == i)
					dfs2(i, j, y, 1);
			}
			for (o = eo[i]; o--; ) {
				j = ej[i][o];
				if (pp[j] == i && tb[j] >= ta[i])
					dfs2(i, j, y, 1);
			}
			k = a, dfs2(i, pp[i], x, 0);
			return xx;
		}
	}
	fill_n(xx.begin(), n, 0);
	return xx;
}

Compilation message (stderr)

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

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