Submission #647491

#	Time	Username	Problem	Language	Result	Execution time	Memory
647491		LucaIlie	Speedrun (RMI21_speedrun)	C++17	100 / 100	239 ms	804 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

const int maxN = 1000;
const int maxLogN = 10;

int parent[maxN];
vector <int> ord;
vector <int> edges[maxN + 1];

void setHints( int u, int p, int v ) {
	for ( int b = 0; b < maxLogN; b++ )
		setHint( u, b + 1, (p >> b) & 1 );
	for ( int b = 0; b < maxLogN; b++ )
		setHint( u, b + 1 + maxLogN, (v >> b) & 1 );
}

void dfsAssignHints( int u, int p ) {
	parent[u] = p;
	ord.push_back( u );
	for ( auto v: edges[u] ) {
		if ( v != p )
			dfsAssignHints( v, u );
	}
}

void assignHints( int subtask, int n, int a[], int b[] ) {
	for ( int i = 1; i <= n - 1; i++ ) {
		edges[a[i]].push_back( b[i] );
		edges[b[i]].push_back( a[i] );
	}

	setHintLen( 2 * maxLogN );
	dfsAssignHints( 1, 0 );
	for ( int i = 0; i < n; i++ )
		setHints( ord[i], parent[ord[i]], (i < n - 1 ? ord[i + 1] : 0) );
}

bool visited[maxN + 1];

int getParent() {
	int p = 0;

	for ( int b = 0; b < maxLogN; b++ )
		p += (getHint( b + 1 ) << b);

	return p;
}
int getNextOrd() {
    int v;

	v = 0;
	for ( int b = 0; b < maxLogN; b++ )
		v += (getHint( b + 1 + maxLogN ) << b);

	return v;
}

void speedrun( int subtask, int n, int start ) {
	int u = start, p = getParent();

	while ( p != 0 ) {
		u = p;
		goTo( u );
		p = getParent();
	}

	u = getNextOrd();
	while ( u != 0 ) {
		while ( !goTo( u ) ) {
			p = getParent();
			goTo( p );
		}
		u = getNextOrd();
	}
}

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