oj.uz

Submission #1034348

# Submission time Handle Problem Language Result Execution time Memory
1034348 2024-07-25T12:32:04 Z andrei_c1 Speedrun (RMI21_speedrun) C++17
100 / 100
 127 ms 1196 KB 
#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

void assignHints(int subtask, int n, int a[], int b[]) { /* your solution here */
	vector<int> ord, up(n + 1);
	vector<vector<int>> adj(n + 1);
	for(int i = 1; i < n; i++) {
		adj[a[i]].emplace_back(b[i]);
		adj[b[i]].emplace_back(a[i]);
	}
	auto dfs = [&](auto &&self, int u) -> void {
		ord.emplace_back(u);
		for(const auto &it: adj[u]) if(it != up[u]) {
			up[it] = u;
			self(self, it);
		}
	};
	dfs(dfs, 1);
	setHintLen(20);
	auto setHintUp = [&](int u, int val) -> void {
		for(int i = 0; i < 10; i++) {
			setHint(u, i + 1, val >> i & 1);
		}
	};
	auto setHintNext = [&](int u, int val) -> void {
		for(int i = 0; i < 10; i++) {
			setHint(u, i + 11, val >> i & 1);
		}
	};
	for(int i = 1; i <= n; i++) {
		setHintUp(i, up[i]);
		setHintNext(ord[i - 1], ord[i % n]);
	}
}

void speedrun(int subtask, int n, int u) { /* your solution here */
	auto getHintUp = [&]() -> int {
		int res = 0;
		for(int i = 0; i < 10; i++) {
			res |= getHint(i + 1) << i;
		}
		return res;
	};
	auto getHintNext = [&]() -> int {
		int res = 0;
		for(int i = 0; i < 10; i++) {
			res |= getHint(i + 11) << i;
		}
		return res;
	};
	while(u != 1) {
		u = getHintUp();
		goTo(u);
	}
	do {
		int nxt = getHintNext();
		while(!goTo(nxt)) {
			u = getHintUp();
			goTo(u);
		}
		u = nxt;
	} while(u != 1);
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1076 KB Output is correct
2 Correct 114 ms 744 KB Output is correct
3 Correct 107 ms 828 KB Output is correct
4 Correct 107 ms 688 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 1084 KB Output is correct
2 Correct 112 ms 700 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 1196 KB Output is correct
2 Correct 113 ms 744 KB Output is correct
3 Correct 127 ms 744 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 98 ms 860 KB Output is correct
2 Correct 105 ms 876 KB Output is correct
3 Correct 94 ms 824 KB Output is correct
4 Correct 104 ms 684 KB Output is correct
5 Correct 107 ms 824 KB Output is correct
6 Correct 89 ms 836 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 944 KB Output is correct
2 Correct 109 ms 1084 KB Output is correct
3 Correct 99 ms 1000 KB Output is correct
4 Correct 100 ms 840 KB Output is correct
5 Correct 110 ms 848 KB Output is correct
6 Correct 120 ms 1192 KB Output is correct
7 Correct 97 ms 688 KB Output is correct