oj.uz

Submission #924174

# Submission time Handle Problem Language Result Execution time Memory
924174 2024-02-08T15:51:48 Z LCJLY Speedrun (RMI21_speedrun) C++14
100 / 100
 76 ms 1964 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;
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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1604 KB Output is correct
2 Correct 55 ms 948 KB Output is correct
3 Correct 76 ms 1700 KB Output is correct
4 Correct 51 ms 1464 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 1120 KB Output is correct
2 Correct 53 ms 1708 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 1196 KB Output is correct
2 Correct 48 ms 952 KB Output is correct
3 Correct 54 ms 1456 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 1376 KB Output is correct
2 Correct 52 ms 1608 KB Output is correct
3 Correct 57 ms 1196 KB Output is correct
4 Correct 63 ms 1204 KB Output is correct
5 Correct 48 ms 1964 KB Output is correct
6 Correct 48 ms 1716 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 940 KB Output is correct
2 Correct 59 ms 1196 KB Output is correct
3 Correct 49 ms 1468 KB Output is correct
4 Correct 57 ms 1456 KB Output is correct
5 Correct 56 ms 1196 KB Output is correct
6 Correct 63 ms 1460 KB Output is correct
7 Correct 49 ms 1196 KB Output is correct