oj.uz

Submission #647491

# Submission time Handle Problem Language Result Execution time Memory
647491 2022-10-02T19:42:20 Z LucaIlie Speedrun (RMI21_speedrun) C++17
100 / 100
 239 ms 804 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 676 KB Output is correct
2 Correct 207 ms 672 KB Output is correct
3 Correct 186 ms 804 KB Output is correct
4 Correct 220 ms 788 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 720 KB Output is correct
2 Correct 239 ms 792 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 792 KB Output is correct
2 Correct 175 ms 740 KB Output is correct
3 Correct 124 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 716 KB Output is correct
2 Correct 215 ms 672 KB Output is correct
3 Correct 200 ms 748 KB Output is correct
4 Correct 102 ms 776 KB Output is correct
5 Correct 203 ms 752 KB Output is correct
6 Correct 195 ms 720 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 672 KB Output is correct
2 Correct 178 ms 716 KB Output is correct
3 Correct 146 ms 744 KB Output is correct
4 Correct 200 ms 712 KB Output is correct
5 Correct 189 ms 672 KB Output is correct
6 Correct 192 ms 708 KB Output is correct
7 Correct 102 ms 796 KB Output is correct