Submission #696199

#	Time	Username	Problem	Language	Result	Execution time	Memory
696199		rainboy	Snowy Roads (JOI16_snowy)	C++17	100 / 100	18 ms	1820 KiB

Anya

#include "Anyalib.h"
#include <stdlib.h>
#include <string.h>

static const int N = 500, L = 9;	/* L = ceil(log2(N)) */

static int ij[N - 1], cc[N - 1];
static int *eh[N], eo[N], n;

static void append(int i, int h) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

static int ll[N], hh[N], qq[N];

static int dfs1(int p, int l, int q, int i) {
	if (ll[i]) {
		bool win = true;
		for (int o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ij[h];
			if (j != p && !dfs1(i, l, q, j))
				win = false;
		}
		return win;
	} else {
		bool win = q == -1;
		for (int o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ij[h];
			if (j != p && !dfs1(i, l, i, j))
				win = true;
		}
		if (!win)
			ll[i] = l, qq[i] = q;
		return win;
	}
}

static void dfs2(int p, int i, int c) {
	for (int l = 0; l < ll[i]; l++)
		Save(hh[i] + l, c >> l & 1);
	for (int o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];
		if (j != p)
			dfs2(i, j, c + cc[h]);
	}
}

void InitAnya(int n_, int *ii, int *jj) {
	n = n_;
	for (int i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (int h = 0; h < n - 1; h++)
		ij[h] = ii[h] ^ jj[h];
	for (int h = 0; h < n - 1; h++)
		append(ii[h], h), append(jj[h], h);
	for (int l = 1; l <= L; l++)
		dfs1(-1, l, -1, 0);
	hh[0] = 0;
	for (int i = 1; i < n; i++)
		hh[i] = hh[i - 1] + ll[i - 1];
}

void Anya(int *cc_) {
	memcpy(cc, cc_, (n - 1) * sizeof *cc_);
	dfs2(-1, 0, 0);
}

Boris

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

static const int N = 500, L = 9;	/* L = ceil(log2(N)) */

static int ij[N - 1];
static int *eh[N], eo[N], n;

static void append(int i, int h) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		eh[i] = (int *) realloc(eh[i], o * 2 * sizeof *eh[i]);
	eh[i][o] = h;
}

static int ll[N], hh[N], qq[N];

static int dfs1(int p, int l, int q, int i) {
	if (ll[i]) {
		bool win = true;
		for (int o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ij[h];
			if (j != p && !dfs1(i, l, q, j))
				win = false;
		}
		return win;
	} else {
		bool win = q == -1;
		for (int o = eo[i]; o--; ) {
			int h = eh[i][o], j = i ^ ij[h];
			if (j != p && !dfs1(i, l, i, j))
				win = true;
		}
		if (!win)
			ll[i] = l, qq[i] = q;
		return win;
	}
}

static int query(int i, int l) {
	if (i == 0)
		return 0;
	int d = query(qq[i], ll[i] - 1);
	if (Ask(hh[i] + ll[i] - 1) != (d >> ll[i] - 1 & 1))
		d += 1 << ll[i] - 1;
	for (int l_ = ll[i] - 2; l_ >= l; l_--)
		if (Ask(hh[i] + l_))
			d |= 1 << l_;
	return d;
}

void InitBoris(int n_, int *ii, int *jj) {
	n = n_;
	for (int i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (int h = 0; h < n - 1; h++)
		ij[h] = ii[h] ^ jj[h];
	for (int h = 0; h < n - 1; h++)
		append(ii[h], h), append(jj[h], h);
	for (int l = 1; l <= L; l++)
		dfs1(-1, l, -1, 0);
	hh[0] = 0;
	for (int i = 1; i < n; i++)
		hh[i] = hh[i - 1] + ll[i - 1];
}

int Boris(int i) {
	return query(i, 0);
}

Compilation message (stderr)

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

Boris.cpp: In function 'void append(int, int)':
Boris.cpp:11:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   11 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Boris.cpp: In function 'int query(int, int)':
Boris.cpp:44:44: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   44 |  if (Ask(hh[i] + ll[i] - 1) != (d >> ll[i] - 1 & 1))
      |                                      ~~~~~~^~~
Boris.cpp:45:19: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   45 |   d += 1 << ll[i] - 1;
      |             ~~~~~~^~~

• Subtask 1: 15 / 15
• Subtask 2: 5 / 5
• Subtask 3: 35 / 35
• Subtask 4: 45 / 45