oj.uz

답안 #737107

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
737107 2023-05-06T15:54:21 Z mjhmjh1104 Speedrun (RMI21_speedrun) C++17
0 / 100
 443 ms 776 KB 
#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);
}

Subtask #1
0.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 176 ms 672 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 161 ms 776 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 209 ms 740 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 443 ms 740 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 212 ms 672 KB Used too many wrong interactions
2 Halted 0 ms 0 KB -