Submission #538496

#	Time	Username	Problem	Language	Result	Execution time	Memory
538496		ddy888	Speedrun (RMI21_speedrun)	C++17	0 / 100	52 ms	780 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];

void init(int x, int p) {
	int tmp = x, bit = 1;
	while (tmp != 0) {
		if (tmp % 2) setHint(p, bit, 1);
		++bit;
		tmp /= 2;
	}
}

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

void dfs(int x, int p) {
	if (x != 1) init(x, lst); // lst -> x
	lst = 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 */
	vector<int> path;
	set<int> vis;
	path.pb(start);
	vis.insert(start);
	int node = start;
	while (1) {
		node = getval();
		while (!goTo(node)) { // backtrack
			goTo(path.back());
			path.pop_back();
		}
		path.pb(node);
		vis.insert(node);
		if ((int)vis.size() == N) break;
	}
}

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