Submission #538178

#	Time	Username	Problem	Language	Result	Execution time	Memory
538178		hmm789	Speedrun (RMI21_speedrun)	C++14	100 / 100	181 ms	832 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1000];
int pre[1000], cur, vtx[1000];

void dfs(int x, int p) {
	vtx[cur] = x;
	pre[x] = cur++;
	int tmp = p, pwr = 1;
	if(tmp == -1) tmp = 1023;
	while(tmp > 0) {
		setHint(x+1, pwr, tmp%2);
		tmp /= 2;
		pwr++;
	}
	for(auto i : adj[x]) if(i != p) dfs(i, x);
}

void assignHints(int subtask , int N, int A[], int B[]) {
	setHintLen(20);
	for(int i = 1; i < N; i++) {
		adj[A[i]-1].push_back(B[i]-1);
		adj[B[i]-1].push_back(A[i]-1);
	}
	dfs(0, -1);
	for(int i = 0; i < N; i++) {
		int tmp, pwr = 11;
		if(pre[i] == N-1) tmp = vtx[0];
		else tmp = vtx[pre[i]+1];
		while(tmp > 0) {
			setHint(i+1, pwr, tmp%2);
			tmp /= 2;
			pwr++;
		}
	}
}


void speedrun(int subtask , int N, int start) {
	start--;
	int cur = start, nxt;
	do {
		nxt = 0;
		for(int i = 11; i <= 20; i++) nxt += getHint(i) * (1<<(i-11));
		while(!goTo(nxt+1)) {
			int p = 0;
			for(int i = 1; i <= 10; i++) p += getHint(i) * (1<<(i-1));
			goTo(p+1);
		}
		cur = nxt;
	} while(cur != start);
}

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