Submission #1116937

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116937		StefanSebez	Speedrun (RMI21_speedrun)	C++14	90 / 100	586 ms	1616 KiB

speedrun

#include<bits/stdc++.h>
#include "speedrun.h"
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1050;
vector<int>E[N],cvorovi;
int par[N];
void DFS(int u,int parent){
	cvorovi.pb(u);
	par[u]=parent;
	for(auto i:E[u]){
		if(i==parent) continue;
		DFS(i,u);
	}
}
void DFS1(int u,int parent){
	for(int i=0;i<E[u].size();i++){
		if(E[u][i]==parent) swap(E[u][i],E[u].back());
	}
	for(auto i:E[u]) if(i!=parent) DFS1(i,u);
}
void assignHints(int subtask, int n, int A[], int B[]) {
	for(int i=1;i<n;i++){E[A[i]].pb(B[i]),E[B[i]].pb(A[i]);}
	if(subtask==2){
		int root=1;
		for(int i=1;i<=n;i++) if(E[i].size()>1) root=i;
		setHintLen(20);
		for(int i=1;i<=n;i++){
			if(i==root){
				setHint(i,1,1);
				continue;
			}
			for(int j=2,x=root;j<=11;j++,x>>=1) setHint(i,j,x&1);
		}
	}
	else if(subtask==3){
		int root=1;
		for(int i=1;i<=n;i++) if(E[i].size()==1) {root=i;}
		//printf("%i\n",root);
		DFS1(root,0);
		//for(int i=1;i<=n;i++) {printf("%i: ",i);for(auto j:E[i]) printf("%i ",j);printf("\n");}
		setHintLen(20);
		for(int i=1;i<=n;i++){
			int ct=1;
			for(auto u:E[i]){
				for(int x=u,cnt=1;cnt<=10;cnt++,ct++,x>>=1){
					setHint(i,ct,x&1);
				}
			}
		}
	}
	else{
		DFS(1,0);
		setHintLen(30);
		for(int i=1;i<=n;i++){
			for(int j=1,u=par[i];j<=10;j++,u>>=1){
				setHint(i,j,u&1);
			}
		}
		for(int I=0;I<n-1;I++){
			int i=cvorovi[I];
			int u=cvorovi[I+1],v=par[u];
			for(int j=11;j<=20;j++,v>>=1){
				setHint(i,j,v&1);
			}
			for(int j=21;j<=30;j++,u>>=1){
				setHint(i,j,u&1);
			}
		}
	}
}

void speedrun(int subtask, int n, int start) {
	if(subtask==2){
		int U=start;
		if(getHint(1)==0){
			int u=0;for(int j=2;j<=11;j++) u+=getHint(j)*(1<<(j-2));
			goTo(u);
			U=u;
		}
		for(int i=1;i<=n;i++){
			if(i==U) continue;
			goTo(i);
			goTo(U);
		}
	}
	else if(subtask==3){
		int U=start;
		while(1){
			int u=0;for(int j=1;j<=10;j++) u+=getHint(j)*(1<<(j-1));
			int v=0;for(int j=11;j<=20;j++) v+=getHint(j)*(1<<(j-11));
			//printf("%i: %i %i\n",U,u,v);
			goTo(u);
			U=u;
			if(u==0||v==0) break;
		}
		while(1){
			int u=0;for(int j=1;j<=10;j++) u+=getHint(j)*(1<<(j-1));
			int v=0;for(int j=11;j<=20;j++) v+=getHint(j)*(1<<(j-11));
			//printf("%i: %i %i\n",U,u,v);
			if(u==0||v==0) break;
			goTo(v);
			U=v;
		}
	}
	else{
		int U=start;
		while(U!=1){
			int v=0;for(int j=1;j<=10;j++) v+=getHint(j)*(1<<(j-1));
			goTo(v);
			U=v;
		}
		int par[n+10]={0},ct=n-1;
		while(ct--){
			int u=0;for(int j=11;j<=20;j++) u+=getHint(j)*(1<<(j-11));
			int v=0;for(int j=21;j<=30;j++) v+=getHint(j)*(1<<(j-21));
			while(U!=u){
				goTo(par[U]);
				U=par[U];
			}
			goTo(v);
			U=v;par[v]=u;
		}
	}
}

Compilation message (stderr)

speedrun.cpp: In function 'void DFS1(int, int)':
speedrun.cpp:21:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0;i<E[u].size();i++){
      |              ~^~~~~~~~~~~~
speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:92:7: warning: variable 'U' set but not used [-Wunused-but-set-variable]
   92 |   int U=start;
      |       ^

• Subtask 1: 21 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 30 / 40