oj.uz

Submission #924173

# Submission time Handle Problem Language Result Execution time Memory
924173 2024-02-08T15:51:18 Z LCJLY Speedrun (RMI21_speedrun) C++14
0 / 100
 57 ms 844 KB 
#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;
int check=7;

void dp(int index, int sz, int target){
	if(!check){
		exit(0);
	}
	check--;
	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
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 684 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 700 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 844 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 684 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 688 KB Solution didn't visit every node
2 Halted 0 ms 0 KB -