#include "speedrun.h"
#include <map>
#include <cstdio>
#include <vector>
using namespace std;
int n, res[2][1006], plan[2][1006], curr, _pv[1006];
vector<int> adj[1006];
bool visited[1006], lf[1006], _visited[1006], _lf[1006], _vlf[1006];
void _assign(int x, int y, int z) {
// printf("assign %d <- %d, %d\n", x, y, z);
for (int i = 0; i < 10; i++) setHint(x + 1, y * 10 + i + 1, z & 1 << i ? true : false);
}
void assign(int x, int y, int z) {
plan[y][x] = z;
}
int get(int y) {
int ret = 0;
for (int i = 0; i < 10; i++) ret |= getHint(y * 10 + i + 1) << i;
return ret;
}
int get(int x, int y) {
return res[y][x];
}
void move(int x) {
if (curr != x) goTo(x + 1)/*, printf("%d -> %d\n", curr, x)*/;
curr = x;
if (!visited[x]) {
res[0][x] = get(0);
res[1][x] = get(1);
// printf("move %d <- %d %d\n", x, res[0][x], res[1][x]);
}
visited[x] = true;
}
bool leaf;
void _dfs(int x, int prev = -1) {
_pv[x] = prev;
int pv = -1;
for (auto &i: adj[x]) if (i != prev) {
if (pv == -1) assign(x, 0, i);
else assign(pv, 1, i);
pv = i;
_dfs(i, x);
}
if (pv == -1) {
lf[x] = true;
assign(x, 0, 1023);
} else if (prev == -1) assign(pv, 1, 1023);
else assign(pv, 1, prev);
}
void assignHints(int subtask, int n, int a[], int b[]) {
::n = n;
leaf = false;
for (int i = 1; i < n; i++) {
adj[a[i] - 1].push_back(b[i] - 1);
adj[b[i] - 1].push_back(a[i] - 1);
}
setHintLen(20);
assign(0, 1, 1023);
_dfs(0);
for (int i = 0; i < n; i++) if (lf[i]) {
swap(plan[0][i], plan[1][i]);
plan[1][i] = _pv[i];
if (plan[1][i] == -1) plan[1][i] = 1022;
if (plan[0][i] == 1023) plan[0][i] = 1022;
}
for (int i = 0; i < n; i++) {
_assign(i, 0, plan[0][i]);
_assign(i, 1, plan[1][i]);
}
}
bool isLeaf(int x) {
if (_vlf[x]) return _lf[x];
bool t, leaf = false;
if (get(x, 0) == 1022 || !(t = goTo(get(x, 0) + 1))) leaf = true;
if (t) move(get(x, 0));
_vlf[x] = true;
_lf[x] = leaf;
return leaf;
}
map<int, int> m;
bool t;
void dfs(int x, int depth) {
bool leaf;
int child = -1, nx = -1;
// printf("zai %d\n", x);
next:;
_visited[x] = true;
child = nx = -1;
if (x == -1) return;
leaf = isLeaf(x);
// printf("%d leaf: %d\n", x, leaf);
m[depth] = x;
if (leaf) {
m[depth - 1] = get(x, 1);
if (get(x, 1) != 1022) {
_vlf[get(x, 1)] = true;
_lf[get(x, 1)] = false;
}
nx = get(x, 0);
} else {
child = get(x, 0);
if (child == 1023) child = -1;
nx = get(x, 1);
}
if (nx == 1023 || nx == 1022) nx = -1;
// printf("%d: child %d, nx %d, depth = %d / %d / %d\n", x, child, nx, depth, m[depth - 1], m[depth - 2]);
if (child != -1 && !_visited[child]) {
move(child);
x = child;
depth++;
// puts("go down");
goto next;
}
if (nx != -1 && nx != m[depth - 2]) {
move(m[depth - 1]);
move(nx);
// printf("transport to %d\n", nx);
x = nx;
goto next;
} else m[depth - 2] = nx;
move(m[depth - 1]);
x = m[depth - 1];
depth--;
// puts("go up");
goto next;
}
void speedrun(int subtask, int n, int st) {
::n = n;
leaf = false;
res[0][st - 1] = get(0);
res[1][st - 1] = get(1);
visited[st - 1] = true;
curr = st - 1;
dfs(st - 1, 0);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
176 ms |
672 KB |
Used too many wrong interactions |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
161 ms |
776 KB |
Invalid node index to goTo |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
209 ms |
740 KB |
Used too many wrong interactions |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
443 ms |
740 KB |
Used too many wrong interactions |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
672 KB |
Used too many wrong interactions |
| 2 |
Halted |
0 ms |
0 KB |
- |
