Submission #443574

#	Time	Username	Problem	Language	Result	Execution time	Memory
443574		rainboy	Split the Attractions (IOI19_split)	C++14	40 / 100	93 ms	17972 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;
}

vi xx;

int pp[N], sz[N], sz_[N], ta[N], tb[N], nxt[N], tail[N], time;

char visited[N]; int qu[N], cnt;

void dfs2(int i) {
	int o;

	if (i < 0 || xx[i] != -1 || visited[i])
		return;
	visited[i] = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (ta[j] >= ta[i] && pp[j] != i)
			dfs2(j);
	}
	qu[cnt++] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (ta[j] >= ta[i] && pp[j] == i)
			dfs2(j);
	}
	dfs2(pp[i]);
}

int k;

void dfs3(int i, int x) {
	int o;

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

		dfs3(j, x);
	}
}

int a, b, x, y;

int solve(int i) {
	int i_, h, h_, sum;

	i_ = i, cnt = 0;
	while (1) {
		qu[cnt++] = i_;
		xx[i_] = -1;
		if (i_ == tail[i])
			break;
		i_ = nxt[i_];
	}
	for (h = 0; h < cnt; h++)
		if (sz_[qu[h]] * 2 >= n) {
			if (n - sz_[qu[h]] < a) {
				for (h = 0; h < cnt; h++)
					xx[qu[h]] = 0;
				return 0;
			}
			k = b, xx[qu[h]] = 0, dfs3(qu[h], y);
			for (h_ = 0; h_ < cnt; h_++)
				if (xx[qu[h_]] == -1) {
					for (h = 0; h < cnt; h++)
						if (xx[qu[h]] == -1)
							xx[qu[h]] = 0;
					k = a, dfs3(qu[h_], x);
					break;
				}
			return 1;
		} else if (sz_[qu[h]] * 3 >= n) {
			k = a, xx[qu[h]] = 0, dfs3(qu[h], x);
			for (h_ = 0; h_ < cnt; h_++)
				if (xx[qu[h_]] == -1) {
					for (h = 0; h < cnt; h++)
						if (xx[qu[h]] == -1)
							xx[qu[h]] = 0;
					k = b, dfs3(qu[h_], y);
					break;
				}
			return 1;
		}
	cnt = 0, dfs2(i), visited[i] = 0;
	sum = 0;
	for (h = 0; h < cnt; h++) {
		sum += sz_[qu[h]];
		if (sum * 2 >= n) {
			k = b;
			for (h_ = 0; h_ <= h; h_++)
				xx[qu[h_]] = 0, dfs3(qu[h_], y);
			for (h_ = h + 1; h_ < cnt; h_++)
				xx[qu[h_]] = 0;
			k = a, xx[qu[h + 1]] = 0, dfs3(qu[h + 1], x);
			break;
		} else if (sum * 3 >= n) {
			k = a;
			for (h_ = 0; h_ <= h; h_++)
				xx[qu[h_]] = 0, dfs3(qu[h_], x);
			for (h_ = h + 1; h_ < cnt; h_++)
				xx[qu[h_]] = 0;
			k = b, xx[qu[h + 1]] = 0, dfs3(qu[h + 1], y);
			break;
		}
	}
	return 1;
}

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

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

		if (!ta[j]) {
			if (dfs1(i, j))
				return 1;
			tb[i] = min(tb[i], tb[j]);
			if (tb[j] >= ta[i]) {
				nxt[i] = j, tail[i] = tail[j], sz_[i] = n - sz[j];
				if (solve(i))
					return 1;
			}
		} else if (j != p)
			tb[i] = min(tb[i], ta[j]);
	}
	sz[i] = sz_[i] = 1, tail[i] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (pp[j] == i) {
			sz[i] += sz[j];
			if (tb[j] < ta[i])
				nxt[tail[i]] = j, tail[i] = tail[j];
			else
				sz_[i] += sz[j];
		}
	}
	return 0;
}

vi find_split(int n_, int a_, int b_, int c, vi ii, vi jj) {
	int m = ii.size(), h, i, 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;
	xx.resize(n);
	if (dfs1(-1, 0))
		for (i = 0; i < n; i++)
			if (!xx[i])
				xx[i] = x ^ y;
	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: 0 / 24
• Subtask 5: 0 / 36