Submission #514550

#	Time	Username	Problem	Language	Result	Execution time	Memory
514550		kshitij_sodani	Speedrun (RMI21_speedrun)	C++14	100 / 100	231 ms	860 KiB

speedrun

//#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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40