oj.uz

Submission #736990

# Submission time Handle Problem Language Result Execution time Memory
736990 2023-05-06T12:15:56 Z jk410 Speedrun (RMI21_speedrun) C++17
100 / 100
 249 ms 964 KB 
#include "speedrun.h"
#include <bits/stdc++.h>

using namespace std;

vector<int> edge[1001];
int dfsOrder[1002];
int dfsIdx;
int par[1001];

void dfs(int v) {
	dfsOrder[++dfsIdx] = v;
	for (int i : edge[v]) {
		if (i == par[v])
			continue;
		par[i] = v;
		dfs(i);
	}
}

void assignHints(int subtask, int N, int A[], int B[]) {
	for (int i = 1; i < N; i++) {
		edge[A[i]].push_back(B[i]);
		edge[B[i]].push_back(A[i]);
	}
	setHintLen(20);
	dfs(1);
	dfsOrder[N + 1] = 1;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= 10; j++)
			setHint(dfsOrder[i], j, dfsOrder[i + 1] & (1 << j - 1));
		for (int j = 11; j <= 20; j++)
			setHint(i, j, par[i] & (1 << j - 11));
	}
}

int getNxt() {
	int ret = 0;
	for (int i = 1; i <= 10; i++) {
		if (getHint(i))
			ret |= (1 << i - 1);
	}
	return ret;
}

int getPar() {
	int ret = 0;
	for (int i = 11; i <= 20; i++) {
		if (getHint(i))
			ret |= (1 << i - 11);
	}
	return ret;
}

void speedrun(int subtask, int N, int start) {
	for (int cnt = 1, cur = start; cnt < N; cnt++) {
		int nxt = getNxt();
		if (goTo(nxt)) {
			cur = nxt;
			continue;
		}
		while (1) {
			if (cur == nxt)
				break;
			int par = getPar();
			goTo(par);
			cur = par;
			if (goTo(nxt)) {
				cur = nxt;
				break;
			}
		}
	}
}

Compilation message

speedrun.cpp: In function 'void assignHints(int, int, int*, int*)':
speedrun.cpp:31:54: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   31 |    setHint(dfsOrder[i], j, dfsOrder[i + 1] & (1 << j - 1));
      |                                                    ~~^~~
speedrun.cpp:33:35: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   33 |    setHint(i, j, par[i] & (1 << j - 11));
      |                                 ~~^~~~
speedrun.cpp: In function 'int getNxt()':
speedrun.cpp:41:19: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   41 |    ret |= (1 << i - 1);
      |                 ~~^~~
speedrun.cpp: In function 'int getPar()':
speedrun.cpp:50:19: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |    ret |= (1 << i - 11);
      |                 ~~^~~~

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 800 KB Output is correct
2 Correct 126 ms 676 KB Output is correct
3 Correct 225 ms 672 KB Output is correct
4 Correct 143 ms 672 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 195 ms 788 KB Output is correct
2 Correct 185 ms 676 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 154 ms 764 KB Output is correct
2 Correct 158 ms 868 KB Output is correct
3 Correct 197 ms 676 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 740 KB Output is correct
2 Correct 181 ms 964 KB Output is correct
3 Correct 164 ms 716 KB Output is correct
4 Correct 220 ms 720 KB Output is correct
5 Correct 193 ms 732 KB Output is correct
6 Correct 111 ms 728 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 672 KB Output is correct
2 Correct 249 ms 672 KB Output is correct
3 Correct 155 ms 720 KB Output is correct
4 Correct 226 ms 672 KB Output is correct
5 Correct 218 ms 804 KB Output is correct
6 Correct 207 ms 796 KB Output is correct
7 Correct 238 ms 708 KB Output is correct