Submission #635694

#	Time	Username	Problem	Language	Result	Execution time	Memory
635694		gromperen	Speedrun (RMI21_speedrun)	C++14	100 / 100	222 ms	840 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

int p[MAXN];

vector<int> adj[MAXN];
vector<int> ord;

void dfs(int u, int prev) {
	ord.push_back(u);
	p[u] = prev;
	for (int v : adj[u]) {
		if (v == prev) continue;
		dfs(v, u);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) {
	setHintLen(20);
	for (int i = 1; i < N; ++i) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(1,0);
	for (int i = 1; i <= N; ++i) {
		int cur = ord[i-1];
		int nxt = ord[i%N];
		for (int i = 0; i < 10; ++i) {
			setHint(cur, i+1, nxt & (1<<i));
			setHint(cur, i+11, p[cur] & (1<<i));
		}
	}
}


void speedrun(int subtask, int N, int start) { /* your solution here */
	int cnt = 1;
	while (cnt < N) {
		int nxt = 0;
		for (int i = 0; i < 10; ++i) nxt |= getHint(i+1) << i;
		while(!goTo(nxt)) {
			int p = 0;
			for (int i = 0; i < 10; ++i) p |= getHint(i+11) << i;
			goTo(p);
		}
		cnt++;
	}
}

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