oj.uz

Submission #794706

# Submission time Handle Problem Language Result Execution time Memory
794706 2023-07-26T19:33:54 Z rainboy Speedrun (RMI21_speedrun) C++17
100 / 100
 194 ms 780 KB 
#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

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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 672 KB Output is correct
2 Correct 154 ms 672 KB Output is correct
3 Correct 186 ms 700 KB Output is correct
4 Correct 159 ms 780 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 700 KB Output is correct
2 Correct 164 ms 672 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 680 KB Output is correct
2 Correct 176 ms 672 KB Output is correct
3 Correct 146 ms 712 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 680 KB Output is correct
2 Correct 133 ms 668 KB Output is correct
3 Correct 172 ms 672 KB Output is correct
4 Correct 145 ms 672 KB Output is correct
5 Correct 150 ms 672 KB Output is correct
6 Correct 163 ms 668 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 708 KB Output is correct
2 Correct 167 ms 664 KB Output is correct
3 Correct 164 ms 696 KB Output is correct
4 Correct 194 ms 672 KB Output is correct
5 Correct 150 ms 708 KB Output is correct
6 Correct 191 ms 672 KB Output is correct
7 Correct 165 ms 696 KB Output is correct