Submission #794706

#	Time	Username	Problem	Language	Result	Execution time	Memory
794706		rainboy	Speedrun (RMI21_speedrun)	C++17	100 / 100	194 ms	780 KiB

speedrun

#include "speedrun.h"
#include <cstdlib>
#include <functional>

using namespace std;

void assignHints(int subtask, int n, int ii[], int jj[]) {
	const int N = 1000, L = 10;	/* L = ceil(log2(N)) */
	int *ej[N], eo[N], pp[N], qu[N], cnt;
	function<void(int, int)> 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;
	};
	function<void(int, int)> dfs = [&](int p, int i) {
		pp[i] = p;
		qu[cnt++] = i;
		for (int o = eo[i]; o--; ) {
			int j = ej[i][o];
			if (j != p)
				dfs(i, j);
		}
	};
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
	for (int h = 1; h < n; h++) {
		int i = ii[h] - 1, j = jj[h] - 1;
		append(i, j), append(j, i);
	}
	cnt = 0, dfs(-1, 0);
	setHintLen(L * 2);
	for (int i = 1; i < n; i++)
		for (int l = 0; l < L; l++)
			setHint(i + 1, l + 1, pp[i] >> l & 1);
	for (int h = 0; h < n; h++) {
		int i = qu[h], j = qu[(h + 1) % cnt];
		for (int l = 0; l < L; l++)
			setHint(i + 1, L + l + 1, j >> l & 1);
	}
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

void speedrun(int subtask, int n, int i) {
	const int N = 1000, L = 10;	/* L = ceil(log2(N)) */
	function<int()> get_parent = [&]() {
		int p = 0;
		for (int l = 0; l < L; l++)
			if (getHint(l + 1))
				p |= 1 << l;
		return p;
	};
	function<int()> get_next = [&]() {
		int j = 0;
		for (int l = 0; l < L; l++)
			if (getHint(L + l + 1))
				j |= 1 << l;
		return j;
	};
	i--;
	while (i != 0)
		goTo((i = get_parent()) + 1);
	int j;
	while ((j = get_next()) != 0) {
		while (!goTo(j + 1))
			goTo((i = get_parent()) + 1);
		i = j;
	}
}

Compilation message (stderr)

speedrun.cpp: In lambda function:
speedrun.cpp:12:24: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   12 |   if (o >= 2 && (o & o - 1) == 0)
      |                      ~~^~~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:46:12: warning: unused variable 'N' [-Wunused-variable]
   46 |  const int N = 1000, L = 10; /* L = ceil(log2(N)) */
      |            ^

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40