oj.uz

Submission #635694

# Submission time Handle Problem Language Result Execution time Memory
635694 2022-08-26T16:37:07 Z gromperen Speedrun (RMI21_speedrun) C++14
100 / 100
 222 ms 840 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1005;

int p[MAXN];

vector<int> adj[MAXN];
vector<int> ord;

void dfs(int u, int prev) {
	ord.push_back(u);
	p[u] = prev;
	for (int v : adj[u]) {
		if (v == prev) continue;
		dfs(v, u);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) {
	setHintLen(20);
	for (int i = 1; i < N; ++i) {
		adj[A[i]].push_back(B[i]);
		adj[B[i]].push_back(A[i]);
	}
	dfs(1,0);
	for (int i = 1; i <= N; ++i) {
		int cur = ord[i-1];
		int nxt = ord[i%N];
		for (int i = 0; i < 10; ++i) {
			setHint(cur, i+1, nxt & (1<<i));
			setHint(cur, i+11, p[cur] & (1<<i));
		}
	}
}


void speedrun(int subtask, int N, int start) { /* your solution here */
	int cnt = 1;
	while (cnt < N) {
		int nxt = 0;
		for (int i = 0; i < 10; ++i) nxt |= getHint(i+1) << i;
		while(!goTo(nxt)) {
			int p = 0;
			for (int i = 0; i < 10; ++i) p |= getHint(i+11) << i;
			goTo(p);
		}
		cnt++;
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 712 KB Output is correct
2 Correct 148 ms 820 KB Output is correct
3 Correct 210 ms 684 KB Output is correct
4 Correct 98 ms 684 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 704 KB Output is correct
2 Correct 150 ms 712 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 672 KB Output is correct
2 Correct 195 ms 672 KB Output is correct
3 Correct 199 ms 672 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 676 KB Output is correct
2 Correct 116 ms 672 KB Output is correct
3 Correct 113 ms 708 KB Output is correct
4 Correct 186 ms 800 KB Output is correct
5 Correct 116 ms 712 KB Output is correct
6 Correct 167 ms 840 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 676 KB Output is correct
2 Correct 158 ms 832 KB Output is correct
3 Correct 137 ms 672 KB Output is correct
4 Correct 173 ms 716 KB Output is correct
5 Correct 200 ms 672 KB Output is correct
6 Correct 111 ms 740 KB Output is correct
7 Correct 134 ms 716 KB Output is correct