Submission #538533

#	Time	Username	Problem	Language	Result	Execution time	Memory
538533		ddy888	Speedrun (RMI21_speedrun)	C++17	100 / 100	177 ms	984 KiB

speedrun

#undef _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define fi first
#define si second
#define ar array
typedef pair<int,int> pi;
typedef tuple<int,int,int> ti;  
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {cerr<<" "<<to_string(H);debug_out(T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)

#include "speedrun.h"

int N, lst;
vector<int> adj[1010];
vector<int> path;

void setchild(int u, int v) {
	int tmp = v, bit = 1;
	while (tmp) {
		setHint(u, bit, tmp % 2);
		tmp /= 2;
		++bit;
	}
}

void setpar(int u, int v) {
	int tmp = v, bit = 11;
	while (tmp) {
		setHint(u, bit, tmp % 2);
		tmp /= 2;
		++bit;
	}
}

int getchild() {
	int ret = 0;
	for (int i = 1; i <= 10; ++i) {
		if (getHint(i) == 1) ret += (1 << (i - 1));
	}
	return ret;
}

int getpar() {
	int ret = 0;
	for (int i = 11; i <= 20; ++i) {
		if (getHint(i) == 1) ret += (1 << (i - 11));
	}
	return ret;
}

void dfs(int x, int p) {
	if (path.size()) {
		setchild(path.back(), x);
		setpar(x, p);
	}
	path.pb(x);
	for (auto i: adj[x]) {
		if (i == p) continue;
		dfs(i, x);
	}
}
	
void assignHints(int subtask, int _N, int A[], int B[]) { /* your solution here */
	N = _N;
	for (int i = 1; i < N; ++i) {
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	setHintLen(20);	
	dfs(1, 1);	
}

void speedrun(int subtask, int _N, int start) { /* your solution here */
	set<int> vis;
	vis.insert(start);
	while ((int)vis.size() != _N) {
		int node = getchild();
		if (node == 0) {
			while (node != 1) {
				node = getpar();
				goTo(node);
				vis.insert(node);
			}
		} else {
			while (!goTo(node)) {
				vis.insert(getpar());
				goTo(getpar());
			}
		}
		vis.insert(node);
	}
}

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