제출 #498717

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
498717		amunduzbaev	Speedrun (RMI21_speedrun)	C++14	100 / 100	278 ms	908 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; //, par;

void dfs(int u, int p = -1){
	cur = 0; // , par = 0;
	for(int j=0;j<10;j++){
		if(getHint(j + 11)) cur |= (1 << j);
	}
	
	while(cur != p && 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
4 5
1

*/

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