Submission #1217871

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217871		zhiganov_v	Speedrun (RMI21_speedrun)	C++20	100 / 100	56 ms	576 KiB

speedrun

#include "speedrun.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_map>
#include <string>
#include <cmath>
#include <iomanip>
#include <array>
#include <queue>
#include <random>
#include <time.h>

#define all(a) a.begin(), a.end()
using namespace std;
typedef long long ll;
typedef long double ld;

void dfs(int v, const vector<vector<int>>& g,
	vector<int>& pr, vector<int>& obx) {
	obx.push_back(v);
	for (int u : g[v]) {
		if (u != pr[v]) {
			pr[u] = v;
			dfs(u, g, pr, obx);
		}
	}
}

void assignHints(int subtask, int N, int A[], int B[]) {
	vector<vector<int>> g(N + 1);
	for (int i = 1; i < N; i++) {
		g[A[i]].push_back(B[i]);
		g[B[i]].push_back(A[i]);
	}
	vector<int> pr(N + 1), obx;
	pr[1] = 1;
	dfs(1, g, pr, obx);
	setHintLen(20);
	for (int v = 1; v <= N; v++) {
		for (int c = 0; c < 10; c++) {
			setHint(v, c + 1, (pr[v] >> c) & 1);
		}
	}
	for (int i = 0; i + 1 < obx.size(); i++) {
		for (int c = 0; c < 10; c++) {
			setHint(obx[i], c + 11, (obx[i + 1] >> c) & 1);
		}
	}
}

int getpr() {
	int res = 0;
	for (int c = 0; c < 10; c++) {
		res |= (int)getHint(c + 1) << c;
	}
	return res;
}

int gettarget() {
	int res = 0;
	for (int c = 0; c < 10; c++) {
		res |= (int)getHint(c + 11) << c;
	}
	return res;
}

void speedrun(int subtask, int N, int start) {
	int v = start;
	while (v > 1) {
		int pr = getpr();
		bool b = goTo(pr);
		if (!b) exit(-1);
		v = pr;
	}
	while (true) {
		int tar = gettarget();
		if (tar == 0) break;
		while (!goTo(tar)) {
			v = getpr();
			goTo(v);
		}
		v = tar;
	}
}

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