Submission #925588

#	Time	Username	Problem	Language	Result	Execution time	Memory
925588		penguin133	Speedrun (RMI21_speedrun)	C++17	100 / 100	71 ms	2892 KiB

speedrun

#include <bits/stdc++.h>
using namespace std;
#include "speedrun.h"
int S[1005], back[1005], cnt = 1;
vector <int> adj[1005];
void dfs(int x, int par){
	S[x] = cnt++;
	for(int i = 0; i < 10; i++)if(par >> i & 1)setHint(x, i + 1, 1);
	for(auto i : adj[x]){
		if(i == par)continue;
		dfs(i, x);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	setHintLen(20);
	for(int i = 1; i <= N - 1; i++)adj[A[i]].push_back(B[i]), adj[B[i]].push_back(A[i]);
	dfs(1, 0);
	for(int i = 1; i <= N; i++)back[S[i]] = i;
	for(int i = 1; i <= N; i++){
		int x = back[S[i] + 1];
		for(int j = 0; j < 10; j++)if(x >> j & 1)setHint(i, j + 11, 1);
	}
}

int vis[1005];
void bruh(int x, int par, set <int> &pos){
	vis[x] = 1;
	int cnt = 0;
	for(int i = 11; i <= 20; i++)if(getHint(i))cnt += (1ll << (i - 11));
	
	int cnt2 = 0;
	for(int i = 1; i <= 10; i++)if(getHint(i))cnt2 += (1ll << (i - 1));

	set <int> cry;
	if(!vis[cnt]){
		bool ok = goTo(cnt);
		if(ok)bruh(cnt, x, pos);
		else pos.insert(cnt), cry.insert(cnt);
	}
	while(1){
		bool f = 0;
		for(auto i : pos){
			if(cry.find(i) != cry.end())continue;
			cry.insert(i);
			if(vis[i])continue;
			bool ok = goTo(i);
			if(ok){
				int tmp = i;
				pos.erase(i);
				bruh(tmp, x, pos);
				f = 1;
				break;
			}
		}
		if(!f)break;
	}
	if(!vis[cnt2]){
		bool ok = goTo(cnt2);
		if(ok)bruh(cnt2, x, pos);
	}
	if(par != -1)goTo(par);
}

void speedrun(int subtask, int N, int start) { /* your solution here */
	set <int> br;
	vis[0] = vis[N + 1] = 1;
	bruh(start, -1, br);
}

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