oj.uz

Submission #538178

# Submission time Handle Problem Language Result Execution time Memory
538178 2022-03-16T07:32:54 Z hmm789 Speedrun (RMI21_speedrun) C++14
100 / 100
 181 ms 832 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

vector<int> adj[1000];
int pre[1000], cur, vtx[1000];

void dfs(int x, int p) {
	vtx[cur] = x;
	pre[x] = cur++;
	int tmp = p, pwr = 1;
	if(tmp == -1) tmp = 1023;
	while(tmp > 0) {
		setHint(x+1, pwr, tmp%2);
		tmp /= 2;
		pwr++;
	}
	for(auto i : adj[x]) if(i != p) dfs(i, x);
}

void assignHints(int subtask , int N, int A[], int B[]) {
	setHintLen(20);
	for(int i = 1; i < N; i++) {
		adj[A[i]-1].push_back(B[i]-1);
		adj[B[i]-1].push_back(A[i]-1);
	}
	dfs(0, -1);
	for(int i = 0; i < N; i++) {
		int tmp, pwr = 11;
		if(pre[i] == N-1) tmp = vtx[0];
		else tmp = vtx[pre[i]+1];
		while(tmp > 0) {
			setHint(i+1, pwr, tmp%2);
			tmp /= 2;
			pwr++;
		}
	}
}


void speedrun(int subtask , int N, int start) {
	start--;
	int cur = start, nxt;
	do {
		nxt = 0;
		for(int i = 11; i <= 20; i++) nxt += getHint(i) * (1<<(i-11));
		while(!goTo(nxt+1)) {
			int p = 0;
			for(int i = 1; i <= 10; i++) p += getHint(i) * (1<<(i-1));
			goTo(p+1);
		}
		cur = nxt;
	} while(cur != start);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 672 KB Output is correct
2 Correct 170 ms 832 KB Output is correct
3 Correct 169 ms 704 KB Output is correct
4 Correct 167 ms 672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 676 KB Output is correct
2 Correct 151 ms 724 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 820 KB Output is correct
2 Correct 148 ms 672 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 155 ms 712 KB Output is correct
2 Correct 175 ms 748 KB Output is correct
3 Correct 153 ms 684 KB Output is correct
4 Correct 162 ms 792 KB Output is correct
5 Correct 157 ms 724 KB Output is correct
6 Correct 181 ms 684 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 724 KB Output is correct
2 Correct 130 ms 700 KB Output is correct
3 Correct 164 ms 676 KB Output is correct
4 Correct 123 ms 784 KB Output is correct
5 Correct 138 ms 732 KB Output is correct
6 Correct 155 ms 672 KB Output is correct
7 Correct 163 ms 724 KB Output is correct