oj.uz

Submission #871709

# Submission time Handle Problem Language Result Execution time Memory
871709 2023-11-11T10:59:34 Z TAhmed33 Speedrun (RMI21_speedrun) C++17
100 / 100
 68 ms 2196 KB 
#include <bits/stdc++.h>
using namespace std;
#include "speedrun.h"
vector <int> adj[2001];
int parent[2001];
vector <int> ord;
void dfs (int pos, int par) {
	for (int i = 1; i <= 10; i++) {
		if (par & (1 << (i - 1))) {
			setHint(pos, i, 1);
		}
	}
	ord.push_back(pos);
	for (auto j : adj[pos]) {
		if (j != par) dfs(j, pos);
	}
}
void assignHints (int subtask, int n, int a[], int b[]) {
	if (n == 1) return;
	for (int i = 1; i < n; i++) {
		adj[a[i]].push_back(b[i]);
		adj[b[i]].push_back(a[i]);
	}
	setHintLen(20);
	dfs(1, 0);	
	for (int i = 1; i < n; i++) {
		int x = ord[i];
		for (int j = 1; j <= 10; j++) {
			if (x & (1 << (j - 1))) {
				setHint(ord[i - 1], j + 10, 1);
			}
		}
	}
}
int getpar () {
	int ret = 0;
	for (int i = 10; i >= 1; i--) {
		ret *= 2; ret += getHint(i);
	}
	return ret;
}
int getnext () {
	int ret = 0;
	for (int i = 20; i >= 11; i--) {
		ret *= 2; ret += getHint(i);
	}
	return ret;
}
void speedrun (int subtask, int n, int start) {
	while (start > 1) {
		start = getpar();
		goTo(start);
	}
	for (int i = 2; i <= n; i++) {
		int x = getnext();
		while (goTo(x) == 0) goTo(getpar());
	}
}

Subtask #1
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 1672 KB Output is correct
2 Correct 49 ms 1692 KB Output is correct
3 Correct 61 ms 2104 KB Output is correct
4 Correct 55 ms 1676 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 1684 KB Output is correct
2 Correct 44 ms 1864 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2188 KB Output is correct
2 Correct 56 ms 1936 KB Output is correct
3 Correct 56 ms 2112 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1852 KB Output is correct
2 Correct 60 ms 1608 KB Output is correct
3 Correct 68 ms 1440 KB Output is correct
4 Correct 57 ms 2196 KB Output is correct
5 Correct 55 ms 1352 KB Output is correct
6 Correct 66 ms 1424 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 1420 KB Output is correct
2 Correct 56 ms 1864 KB Output is correct
3 Correct 49 ms 1860 KB Output is correct
4 Correct 52 ms 1872 KB Output is correct
5 Correct 57 ms 1420 KB Output is correct
6 Correct 53 ms 2184 KB Output is correct
7 Correct 57 ms 1616 KB Output is correct