Submission #498711

#	Time	Username	Problem	Language	Result	Execution time	Memory
498711		amunduzbaev	Speedrun (RMI21_speedrun)	C++14	0 / 100	936 ms	788 KiB

speedrun

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

#ifndef EVAL
#include "grader.cpp"
#endif

void assignHints(int subtask, int n, int a[], int b[]) {
	vector<vector<int>> edges(n + 1);
	vector<int> par(n + 1), tt, nxt(n + 1);
	for(int i=1;i<n;i++){
		edges[a[i]].push_back(b[i]);
		edges[b[i]].push_back(a[i]);
	}
	
	function<void(int, int)> dfs = [&](int u, int p){
		tt.push_back(u), par[u] = p;
		for(auto x : edges[u]){
			if(x == p) continue;
			dfs(x, u);
		}
	};
	
	dfs(1, 1);
	int p = 0;
	for(auto x : tt) nxt[p] = x, p = x;
	nxt[p] = 1;
	
	setHintLen(20);
	for(int i=1;i<=n;i++){
		for(int j=0;j<10;j++){
			setHint(i, j + 1, par[i]>>j&1);
		}
		
		for(int j=0;j<10;j++){
			setHint(i, j + 11, nxt[i]>>j&1);
		}
	}
}

int cur;

void dfs(int u, int p = -1){
	int x = 0;
	for(int j=0;j<10;j++) x |= (getHint(j + 11) << j);
	cur = x;
	while(goTo(cur)) dfs(cur, u);
	if(~p) goTo(p);
}

void speedrun(int subtask, int n, int u) {
	while(u != 1){
		int par = 0;
		for(int j=0;j<10;j++) par |= (getHint(j + 1) << j);
		goTo(par), u = par;
	}
	
	dfs(u);
}

/*

5
1 2
2 3
3 4
3 5
1

*/

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