oj.uz

Submission #514550

# Submission time Handle Problem Language Result Execution time Memory
514550 2022-01-18T09:03:44 Z kshitij_sodani Speedrun (RMI21_speedrun) C++14
100 / 100
 231 ms 860 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second

#include "speedrun.h"
vector<int> adj[1001];
int co=0;
int ind[1001];
int st[1001];
int par[1001];
void dfs(int no,int par2=0){
	st[no]=co;
	ind[co]=no;
	co++;
	par[no]=par2;
	for(auto j:adj[no]){
		if(j!=par2){
			dfs(j,no);
		}
	}
}
void assignHints(int subtask, int n, int aa[], int bb[]) { /* your solution here */
	for(int i=1;i<n;i++){
		adj[aa[i]].pb(bb[i]);
		adj[bb[i]].pb(aa[i]);
	}
	co=0;
	dfs(1);
	setHintLen(20);
		for(int i=1;i<=n;i++){
			//cout<<par[i]<<":"<<st[i]<<endl;
			for(int k=0;k<10;k++){
				if((1<<k)&par[i]){
					setHint(i,k+1,1);
				}
				else{
					setHint(i,k+1,0);
				}
			}
			for(int k=0;k<10;k++){
				if(st[i]==n-1){
					continue;
				}
				if((1<<k)&ind[st[i]+1]){
					setHint(i,k+11,1);
				}
				else{
					setHint(i,k+11,0);
				}
			}
		}
	
}	

void speedrun(int subtask, int n, int start) { /* your solution here */

	int cur=start;
	while(cur!=1){
		int cur2=0;
		for(int j=1;j<=10;j++){
			int x=getHint(j);
			if(x==1){
				cur2+=(1<<(j-1));
			}
		}
		cur=cur2;
		goTo(cur);
	}
	for(int i=0;i<n-1;i++){
		int ne=0;
		for(int j=11;j<=20;j++){
			int x=getHint(j);
			if(x==1){
				ne+=(1<<(j-11));
			}
		}
		while(goTo(ne)==false){
			int cur2=0;
			for(int j=1;j<=10;j++){
				int x=getHint(j);
				if(x==1){
					cur2+=(1<<(j-1));
				}
			}
			cur=cur2;
			goTo(cur);
		}
		cur=ne;
	}




}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 676 KB Output is correct
2 Correct 123 ms 848 KB Output is correct
3 Correct 180 ms 660 KB Output is correct
4 Correct 210 ms 660 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 692 KB Output is correct
2 Correct 184 ms 860 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 668 KB Output is correct
2 Correct 169 ms 688 KB Output is correct
3 Correct 178 ms 660 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 688 KB Output is correct
2 Correct 181 ms 716 KB Output is correct
3 Correct 187 ms 708 KB Output is correct
4 Correct 179 ms 696 KB Output is correct
5 Correct 192 ms 696 KB Output is correct
6 Correct 162 ms 676 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 704 KB Output is correct
2 Correct 184 ms 788 KB Output is correct
3 Correct 161 ms 708 KB Output is correct
4 Correct 147 ms 660 KB Output is correct
5 Correct 195 ms 704 KB Output is correct
6 Correct 190 ms 660 KB Output is correct
7 Correct 170 ms 744 KB Output is correct