제출 #924174

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924174		LCJLY	Speedrun (RMI21_speedrun)	C++14	100 / 100	76 ms	1964 KiB

speedrun

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

vector<int>adj[1005];
int pp[1005];
int in[1005];
int tour[1005];
int ptr=0;

void dfs(int index, int par){
	in[index]=ptr++;
	tour[in[index]]=index;
	for(auto it:adj[index]){
		if(it==par) continue;
		pp[it]=index;
		dfs(it,index);
	}
}

void assignHints(int subtask, int n, int a[], int b[]) { 
	int temp,temp2;
	for(int x=1;x<=n-1;x++){
		temp=a[x];
		temp2=b[x];
		adj[temp].push_back(temp2);
		adj[temp2].push_back(temp);
	}
	
	dfs(1,-1);
	setHintLen(20);
	for(int x=1;x<=n;x++){
		int cur=in[x];
		//show2(x,x,cur,cur);
		int nxt=tour[(cur+1)%n];
		//show(nxt,nxt);
		for(int y=1;y<=10;y++){
			if(pp[x]&(1<<(y-1))){
				setHint(x,y,1);
				//show2(index,x,bit,y);
			}
		}
		
		for(int y=1;y<=10;y++){
			if(nxt&(1<<(y-1))){
				setHint(x,y+10,1);
				//show2(index,x,bit,y+10);
			}
		}
	}
	//show(done,1);
}

int counter=0;
void dp(int index, int sz, int target){
	if(counter==sz-1) return;
	int par=0;
	int nxt=0;
	for(int x=1;x<=10;x++){
		bool hold=getHint(x);
		if(hold){
			par+=(1<<(x-1));
		}
		hold=getHint(x+10);
		if(hold){
			nxt+=(1<<(x-1));
		}
	}
	//for(int x=1;x<=20;x++){
		//bool hold=getHint(x);
		//cout << hold;
	//}
	//cout << endl;
	//show3(index,index,par,par,nxt,nxt);
	//show(target,target);
	bool amos;
	if(target!=-1){
		amos=goTo(target);
		if(amos){
			counter++;
			dp(target,sz,-1);
		}
		else{
			amos=goTo(par);
			dp(par,sz,target);
		}
		return;
	}
	amos=goTo(nxt);
	if(amos){
		counter++;
		dp(nxt,sz,-1);
	}
	else{
		amos=goTo(par);
		dp(par,sz,nxt);
	}
}

void speedrun(int subtask, int N, int start) { 
	dp(start,N,-1);
}

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