oj.uz

Submission #538428

# Submission time Handle Problem Language Result Execution time Memory
538428 2022-03-16T19:56:26 Z jamielim Speedrun (RMI21_speedrun) C++14
100 / 100
 205 ms 824 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
 
#define pb emplace_back
 
int n;
vector<int> adj[2005];
int par[2005];
vector<int> ord;
int c[2005];
 
void dfs(int x){
	ord.pb(x);
	for(int i:adj[x]){
		if(par[x]==i)continue;
		par[i]=x;
		dfs(i);
	}
}
 
void assignHints(int subtask, int N, int A[], int B[]) {
	n=N;
	for(int i=1;i<n;i++){
		adj[A[i]].pb(B[i]);
		adj[B[i]].pb(A[i]);
	}
	dfs(1);
	par[1]=1;ord.pb(0);
	setHintLen(20);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=10;j++){
			if(par[i]&(1<<(j-1)))setHint(i,j,1);
			else setHint(i,j,0);
		}
		for(int j=11;j<=20;j++){
			if(ord[i]&(1<<(j-11)))setHint(ord[i-1],j,1);
			else setHint(ord[i-1],j,0);
		}
	}
}
 
 
int getParent(){
	int ans=0;
	for(int i=1;i<=10;i++){
		if(getHint(i))ans|=(1<<(i-1));
	}
	return ans;
}
int getNext(){
	int ans=0;
	for(int i=11;i<=20;i++){
		if(getHint(i))ans|=(1<<(i-11));
	}
	return ans;
}
void speedrun(int subtask, int N, int start) {
	int cur=start;
	while(cur!=getParent()&&cur!=1){
		int p=getParent();
		goTo(p);
		cur=p;
	}
	int nxt=getNext();
	while(nxt!=0){
		while(!goTo(nxt)){
			int p=getParent();
			goTo(p);
			cur=p;
		}
		cur=nxt;
		nxt=getNext();
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 672 KB Output is correct
2 Correct 148 ms 736 KB Output is correct
3 Correct 170 ms 752 KB Output is correct
4 Correct 205 ms 736 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 672 KB Output is correct
2 Correct 128 ms 780 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 804 KB Output is correct
2 Correct 162 ms 800 KB Output is correct
3 Correct 135 ms 800 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 736 KB Output is correct
2 Correct 162 ms 744 KB Output is correct
3 Correct 152 ms 740 KB Output is correct
4 Correct 160 ms 684 KB Output is correct
5 Correct 192 ms 696 KB Output is correct
6 Correct 148 ms 732 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 824 KB Output is correct
2 Correct 184 ms 744 KB Output is correct
3 Correct 118 ms 672 KB Output is correct
4 Correct 162 ms 684 KB Output is correct
5 Correct 167 ms 768 KB Output is correct
6 Correct 182 ms 732 KB Output is correct
7 Correct 105 ms 724 KB Output is correct