Submission #585358

#	Time	Username	Problem	Language	Result	Execution time	Memory
585358		rainboy	Game (APIO22_game)	C++17	100 / 100	1363 ms	122448 KiB

game

/* https://codeforces.com/blog/entry/91608 */
#include "game.h"
#include <stdlib.h>

const int N = 300000;

int *ej[N], eo[N], *fi[N], fo[N], ll[N], rr[N], n, k;

void append(int **ej, int *eo, 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 init(int n_, int k_) {
	n = n_, k = k_;
	for (int i = 0; i < n; i++) {
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
		fi[i] = (int *) malloc(2 * sizeof *fi[i]);
	}
	for (int i = 0; i < n; i++)
		if (i < k)
			ll[i] = rr[i] = i;
		else
			ll[i] = -1, rr[i] = k;
}

int add(int i, int j) {
	int m, o;

	if (rr[i] < ll[j])
		return 0;
	if (rr[j] < ll[i])
		return 1;
	if (ll[i] == ll[j] && rr[i] == rr[j])
		return 0;
	if (ll[i] <= ll[j] && rr[j] <= rr[i]) {
		m = ll[i] + (rr[i] - ll[i]) / 2;
		if (rr[j] > m)
			return 0;
		rr[i] = m;
		if (i >= k && ll[i] == rr[i])
			return 1;
		for (o = eo[i]; o--; ) {
			int v = ej[i][o];

			if (add(i, v))
				return 1;
		}
		for (o = fo[i]; o--; ) {
			int u = fi[i][o];

			if (add(u, i))
				return 1;
		}
		return add(i, j);
	} else {
		m = ll[j] + (rr[j] - ll[j]) / 2;
		if (ll[i] <= m)
			return 0;
		ll[j] = m + 1;
		if (j >= k && ll[j] == rr[j])
			return 1;
		for (o = eo[j]; o--; ) {
			int v = ej[j][o];

			if (add(j, v))
				return 1;
		}
		for (o = fo[j]; o--; ) {
			int u = fi[j][o];

			if (add(u, j))
				return 1;
		}
		return add(i, j);
	}
}

int add_teleporter(int i, int j) {
	if (i == j)
		return i < k;
	if (add(i, j))
		return 1;
	append(ej, eo, i, j), append(fi, fo, j, i);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 10 / 10
• Subtask 3: 18 / 18
• Subtask 4: 30 / 30
• Subtask 5: 40 / 40