Submission #1211573

#	Time	Username	Problem	Language	Result	Execution time	Memory
1211573		Muhammad_Aneeq	Speedrun (RMI21_speedrun)	C++20	100 / 100	55 ms	540 KiB

speedrun

#include "speedrun.h"
#include <vector>
#include <map>
#include <set>
using namespace std;
int const MAXN=1e3+10;
vector<int>nei[MAXN]={};
vector<int>ord;
int it[MAXN],ot[MAXN],P[MAXN];
int tm=0;
void dfs(int u,int p=0)
{
	it[u]=tm++;
	P[u]=p;
	ord.push_back(u);
	for  (auto i:nei[u])
	{
		if (i==p) continue;
		dfs(i,u);
	}
	ot[u]=tm-1;
}
void assignHints(int subtask, int N, int A[], int B[]) 
{ 
	setHintLen(20);
	for (int i=1;i<N;i++)
	{
		nei[A[i]].push_back(B[i]);
		nei[B[i]].push_back(A[i]);
	}
	dfs(1);
	ord.push_back(0);
	for (int i=0;i<N;i++)
	{
		int u=ord[i],v=ord[i+1];
		int p=P[u];
		for (int j=1;j<=10;j++)
		{
			bool w=(p&(1<<(j-1)));
			setHint(u,j,w);	
		}
		for (int j=11;j<=20;j++)
		{
			bool w=(v&(1<<(j-11)));
			setHint(u,j,w);
		}
	}
}
void speedrun(int subtask, int N, int s) 
{ 
	set<int>vis;
	vis.insert(s);
	int cur=s;
	int len=getLength();
	while (cur!=1)
	{
		int pr=0;
		vis.insert(cur);
		for (int j=1;j<=10;j++)
		{
			int f=getHint(j);
			pr+=(f<<(j-1));
		}		goTo(pr);
		cur=pr;
	}
	while (vis.size()!=N)
	{
		vis.insert(cur);
		int pr=0,nx=0;
		for (int j=11;j<=20;j++)
		{
			int f=getHint(j);
			nx+=(f<<(j-11));
		}
		if (nx==0)
			break;
		while (!goTo(nx))
		{
			pr=0;
			for (int j=1;j<=10;j++)
			{
				int f=getHint(j);
				pr+=(f<<(j-1));
			}
			goTo(pr);
		}
		cur=nx;
	}
}

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