oj.uz

Submission #518500

# Submission time Handle Problem Language Result Execution time Memory
518500 2022-01-24T00:29:36 Z Rainbowbunny Speedrun (RMI21_speedrun) C++17
100 / 100
 214 ms 824 KB 
#include <bits/stdc++.h>
#include "speedrun.h"
using namespace std;

const int MAXN = 1 << 10;

int tim = 0;
int par[MAXN], order[MAXN];
vector <int> Adj[MAXN];

void DFS(int node, int p = 0)
{
	tim++;
	order[tim] = node;
	par[node] = p;
	for(auto x : Adj[node])
	{
		if(x == p)
		{
			continue;
		}
		DFS(x, node);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) 
{
	setHintLen(20);
	for(int i = 1; i < N; i++)
	{
		Adj[A[i]].push_back(B[i]);
		Adj[B[i]].push_back(A[i]);
	}
	DFS(1);
	for(int i = 1; i <= N; i++)
	{
		int tmp = order[i + 1] + MAXN * par[order[i]];
		for(int j = 0; j < 20; j++)
		{
			int bit = (tmp >> j) & 1;
			setHint(order[i], j + 1, bit);
		}
	}
}

void speedrun(int subtask, int N, int start) 
{
	while(true)
	{
		int tmp = 0;
		for(int j = 1; j <= 20; j++)
		{
			if(getHint(j))
			{
				tmp |= (1 << (j - 1));
			}
		}
		if(tmp / MAXN)
		{
			goTo(tmp / MAXN);
			start = tmp / MAXN;
		}
		else
		{
			break;
		}
	}
	while(true)
	{
		int tmp = 0;
		for(int j = 1; j <= 20; j++)
		{
			if(getHint(j))
			{
				tmp |= (1 << (j - 1));
			}
		}
		int zz = tmp % MAXN;
		if(zz)
		{
			while(true)
			{
				int tt = 0;
				for(int j = 1; j <= 20; j++)
				{
					if(getHint(j))
					{
						tt |= (1 << (j - 1));
					}
				}
				if(goTo(zz))
				{
					start = zz;
					break;
				}
				start = tt / MAXN;
				goTo(start);
			}
		}
		else
		{
			break;
		}
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 712 KB Output is correct
2 Correct 145 ms 660 KB Output is correct
3 Correct 213 ms 676 KB Output is correct
4 Correct 208 ms 680 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 660 KB Output is correct
2 Correct 214 ms 684 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 672 KB Output is correct
2 Correct 194 ms 804 KB Output is correct
3 Correct 99 ms 748 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 752 KB Output is correct
2 Correct 194 ms 660 KB Output is correct
3 Correct 195 ms 704 KB Output is correct
4 Correct 179 ms 660 KB Output is correct
5 Correct 207 ms 660 KB Output is correct
6 Correct 167 ms 684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 744 KB Output is correct
2 Correct 203 ms 660 KB Output is correct
3 Correct 200 ms 824 KB Output is correct
4 Correct 141 ms 696 KB Output is correct
5 Correct 165 ms 708 KB Output is correct
6 Correct 188 ms 712 KB Output is correct
7 Correct 188 ms 704 KB Output is correct