Submission #921519

#	Time	Username	Problem	Language	Result	Execution time	Memory
921519		pavement	Speedrun (RMI21_speedrun)	C++17	100 / 100	128 ms	2292 KiB

speedrun

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

#define pb push_back
#define mp make_pair

using ii = pair<int, int>;

namespace stage_1 {
	int down[1005], nxt[1005], par[1005];
	vector<int> adj[1005];

	void dfs(int u, int e = 0) {
		par[u] = e;
		vector<int> chd;
		for (auto v : adj[u]) if (v != e) {
			chd.pb(v);
			dfs(v, u);
		}
		down[u] = (chd.empty() ? 0 : chd[0]);
		for (int i = 0; i + 1 < (int)chd.size(); i++) {
			nxt[chd[i]] = chd[i + 1];
		}
	}
};

void assignHints(int subtask, int N, int A[], int B[]) {
	setHintLen(20);
	
	if (N == 1) {
		return;
	}
	
	for (int i = 1; i < N; i++) {
		stage_1::adj[A[i]].pb(B[i]);
		stage_1::adj[B[i]].pb(A[i]);
	}
	stage_1::dfs(1);
	for (int i = 1; i <= N; i++) {
		if (stage_1::nxt[i] == 0) {
			if (i == 1) {
				stage_1::nxt[i] = N + 1;
			} else {
				stage_1::nxt[i] = stage_1::par[stage_1::par[i]];
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 10; j++) {
			setHint(i, j, !!(stage_1::down[i] & (1 << (j - 1))));
		}
		for (int j = 11; j <= 20; j++) {
			setHint(i, j, !!(stage_1::nxt[i] & (1 << (j - 11))));
		}
	}
}

namespace stage_2 {
	int N;
	bool vis[1005];
	
	ii unpack() {
		int ret_down = 0, ret_nxt = 0;
		for (int i = 1; i <= 20; i++) {
			if (getHint(i)) {
				if (i <= 10) {
					ret_down |= (1 << (i - 1));
				} else {
					ret_nxt |= (1 << (i - 11));
				}
			}
		}
		return mp(ret_down, ret_nxt);
	};
	
	void dfs(int u, int e = 0) {
		vis[u] = 1;
		
		int tmp_2 = unpack().second;
		
		if (tmp_2 && tmp_2 != N + 1 && !vis[tmp_2]) {
			assert(e);
			goTo(e);
			goTo(tmp_2);
			dfs(tmp_2, e);
			goTo(e);
			goTo(u);
		}
		
		int tmp_1 = unpack().first;
		
		if (tmp_1 == 0) {
			return;
		}
		
		goTo(tmp_1);
		dfs(tmp_1, u);
		goTo(u);
	}
};

void speedrun(int subtask, int N, int start) {
	if (N == 1) {
		return;
	}
	
	stage_2::N = N;
	
	auto [start_down, start_nxt] = stage_2::unpack();
	
	if (start_down == 0) {
		for (int i = 1; i <= N; i++) {
			if (goTo(i)) {
				start = i;
				break;
			}
		}
	}
	
	int u = start;
	
	while (1) {
		auto [cur_down, cur_nxt] = stage_2::unpack();
		
		assert(cur_down);
		
		int v = cur_down, prv_v = -1;
		
		while (1 <= v && v <= N && goTo(v)) {
			prv_v = v;
			v = stage_2::unpack().second;
			goTo(u);
		}
		
		goTo(prv_v);
		u = prv_v;
		
		if (v == 0) {
			break;
		}
	}
	
	assert(goTo(1));
	
	stage_2::dfs(1);
}

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