제출 #1299068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1299068		NotLinux	Speedrun (RMI21_speedrun)	C++20	100 / 100	60 ms	568 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
	vector<vector<int>>tree(N+1);
	for(int i = 1;i<N;i++){
		tree[A[i]].push_back(B[i]);
		tree[B[i]].push_back(A[i]);
	}
	vector<vector<int>>git(N+1,vector<int>(2 , 0));
	vector<int>tour , par(N);

	function<void(int,int)> dfs = [&](int node , int lst){
		tour.push_back(node);
		par[node] = lst;
		for(auto itr : tree[node]){
			if(itr == lst)continue;
			dfs(itr,node);
		}
	};
	dfs(1,0);

	setHintLen(20);
	for(int i = 0;i<sz(tour)-1;i++){
		git[tour[i]][0] = tour[i+1];
	}
	for(int i = 1;i<=N;i++){
		git[i][1] = par[i];
	}

	for(int i = 1;i<=N;i++){
		vector<bool>v;
		for(auto itr : git[i]){
			for(int j = 0;j<10;j++){
				v.push_back(itr & (1 << j));
			}
		}
		for(int j = 0;j<sz(v);j++){
			setHint(i , j+1 , v[j]);
		}
	}
}

void speedrun(int subtask, int N, int node) { /* your solution here */
	auto getnxt = [&](){
		int ret = 0;
		for(int j = 0;j<10;j++){
			ret += (1 << j) * getHint(j+1);
		}
		return ret;
	};
	auto getpar = [&](){
		int ret = 0;
		for(int j = 10;j<20;j++){
			ret += (1 << (j - 10)) * getHint(j+1);
		}
		return ret;
	};
	// cout << "node : " << node << " , par : " << getpar() << endl;
	while(getpar() != 0){
		node = getpar();
		goTo(getpar());
		// cout << "node : " << node << " , par : " << getpar() << endl;
	}
	// cout << "flag" << endl;
	while(getnxt() != 0){
		int nxt = getnxt();
		while(goTo(nxt) == 0){
			node = getpar();
			goTo(getpar());
			// cout << " - node : " << node << " , par : " << getpar() << endl;
		}
		node = nxt;
		// cout << "node : " << node << " , par : " << getpar() << endl;
	}
}

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