Submission #737095

#	Time	Username	Problem	Language	Result	Execution time	Memory
737095		mjhmjh1104	Speedrun (RMI21_speedrun)	C++17	0 / 100	744 ms	2052 KiB

speedrun

#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];

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);
    curr = x;
    if (!visited[x]) {
        res[0][x] = get(0);
        res[1][x] = get(1);
    }
    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) {
    bool t, leaf = false;
    if (get(x, 0) == 1022 || !(t = goTo(get(x, 0) + 1))) leaf = true;
    if (t) move(get(x, 0));
    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:;
    leaf = isLeaf(x);
    m[depth] = x;
    if (leaf) {
        m[depth - 1] = get(x, 1);
        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) {
        move(child);
        dfs(child, depth + 1);
    }
    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]);
    // printf("move up\n");
}

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);
}

• Subtask 1: 0 / 21
• Subtask 2: 0 / 8
• Subtask 3: 0 / 19
• Subtask 4: 0 / 12
• Subtask 5: 0 / 40