Submission #503364

#	Time	Username	Problem	Language	Result	Execution time	Memory
503364		atoiz	Speedrun (RMI21_speedrun)	C++14	100 / 100	231 ms	824 KiB

speedrun

#include "speedrun.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void assignHints(int subtask, int N, int A[], int B[]) {
	setHintLen(20);

	vector<vector<int>> G(N + 1);
	for (int i = 1; i < N; ++i) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}

	int last = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		if (last) for (int i = 0; i < 10; ++i) setHint(last, i + 1, (u >> i) & 1);
		last = u;
		for (int i = 0; i < 10; ++i) setHint(u, i + 11, (p >> i) & 1);
		for (int v : G[u]) if (v != p) dfs(v, u);
	};
	dfs(1, 0);
	setHint(last, 1, 1);
}

void speedrun(int subtask, int N, int start) {
	int cur = start;
	while (true) {
		int target = 0;
		for (int i = 10; i >= 1; --i) target = target * 2 + getHint(i);
		if (target == cur) break;

		while (!goTo(target)) {
			int par = 0;
			for (int i = 20; i >= 11; --i) par = par * 2 + getHint(i);
			goTo(par);
		}
	}
}

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