oj.uz

Submission #503364

# Submission time Handle Problem Language Result Execution time Memory
503364 2022-01-07T17:45:54 Z atoiz Speedrun (RMI21_speedrun) C++14
100 / 100
 231 ms 824 KB 
#include "speedrun.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

using namespace std;

void assignHints(int subtask, int N, int A[], int B[]) {
	setHintLen(20);

	vector<vector<int>> G(N + 1);
	for (int i = 1; i < N; ++i) {
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}

	int last = 0;
	function<void(int, int)> dfs = [&](int u, int p) {
		if (last) for (int i = 0; i < 10; ++i) setHint(last, i + 1, (u >> i) & 1);
		last = u;
		for (int i = 0; i < 10; ++i) setHint(u, i + 11, (p >> i) & 1);
		for (int v : G[u]) if (v != p) dfs(v, u);
	};
	dfs(1, 0);
	setHint(last, 1, 1);
}

void speedrun(int subtask, int N, int start) {
	int cur = start;
	while (true) {
		int target = 0;
		for (int i = 10; i >= 1; --i) target = target * 2 + getHint(i);
		if (target == cur) break;

		while (!goTo(target)) {
			int par = 0;
			for (int i = 20; i >= 11; --i) par = par * 2 + getHint(i);
			goTo(par);
		}
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 704 KB Output is correct
2 Correct 111 ms 728 KB Output is correct
3 Correct 124 ms 744 KB Output is correct
4 Correct 215 ms 724 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 664 KB Output is correct
2 Correct 223 ms 780 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 788 KB Output is correct
2 Correct 160 ms 740 KB Output is correct
3 Correct 187 ms 752 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 684 KB Output is correct
2 Correct 181 ms 672 KB Output is correct
3 Correct 172 ms 688 KB Output is correct
4 Correct 127 ms 740 KB Output is correct
5 Correct 191 ms 728 KB Output is correct
6 Correct 183 ms 704 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 177 ms 776 KB Output is correct
2 Correct 111 ms 700 KB Output is correct
3 Correct 183 ms 824 KB Output is correct
4 Correct 110 ms 736 KB Output is correct
5 Correct 190 ms 708 KB Output is correct
6 Correct 231 ms 704 KB Output is correct
7 Correct 190 ms 748 KB Output is correct