Submission #736990

#	Time	Username	Problem	Language	Result	Execution time	Memory
736990		jk410	Speedrun (RMI21_speedrun)	C++17	100 / 100	249 ms	964 KiB

speedrun

#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 (stderr)

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 / 21
• Subtask 2: 8 / 8
• Subtask 3: 19 / 19
• Subtask 4: 12 / 12
• Subtask 5: 40 / 40