Submission #503403

#	Time	Username	Problem	Language	Result	Execution time	Memory
503403		Stickfish	Speedrun (RMI21_speedrun)	C++17	100 / 100	126 ms	916 KiB

speedrun

#include "speedrun.h"
#include <vector>
#include <cassert>
#include <bitset>
#include <algorithm>
#include <iostream>
using namespace std;

const int MAXN = 1000;
const int LEN = 10;
const int MEM = 20;
vector<int> edg[MAXN];
int root[MAXN];

void dfs_init(int v) {
    for (int i = 0; i < edg[v].size(); ++i) {
        if (edg[v][i] == root[v]) {
            edg[v].erase(edg[v].begin() + i);
            break;
        }
    }
    for (auto u : edg[v]) {
        if (u == root[v])
            continue;
        root[u] = v;
        dfs_init(u);
    }
}

void write(int v, int x, int ps) {
    for (int i = 0; i < LEN; ++i) {
        if (x & (1 << i)) {
            //cout << i + 1 + ps * LEN << endl;
            setHint(v + 1, i + 1 + ps * LEN, 1);
        }
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    for (int i = 1; i < N; ++i) {
        --A[i];
        --B[i];
        edg[A[i]].push_back(B[i]);
        edg[B[i]].push_back(A[i]);
        //cout << A[i] << ' ' << B[i] << endl;
    }
    setHintLen(20);
    dfs_init(0);
    for (int i = 0; i < N; ++i) {
        if (edg[i].size()) {
            write(i, edg[i][0], 0);
            write(edg[i].back(), root[i], 1);
        } else {
            write(i, root[i], 0);
        }
        int s = edg[i].size();
        for (int j = 0; j + 1 < s; ++j) {
            write(edg[i][j], edg[i][(j + 1) % s], 1);
        }
    }
}

bitset<MEM> bs[MAXN];
bitset<MAXN> used;

int read(int v, int ps) {
    if (!used[v]) {
        used[v] = 1;
        for (int i = 0; i < MEM; ++i) {
            bs[v][i] = getHint(i + 1);
        }
    }
    if (ps == 0) {
        return ((bs[v] << LEN) >> LEN).to_ullong();
    } else {
        return (bs[v] >> LEN).to_ullong();
    }
}

void dfs_ans(int v) {
    //cerr << v << endl;
    int u0 = read(v, 0);
    //if (u0 == v) {
        //assert(0);
    //}
    int u = u0;
    int cnt = 0;
    do {
        if (!used[u]) {
            //cout << v << " -> " << u << endl;
            if (!goTo(u + 1)) {
                return;
            }
            dfs_ans(u);
            assert(goTo(v + 1));
        } else {
            //cout << v << " => " << u << endl;
        }
        assert(used[u]);
        if (u == 0)
            return;
        u = read(u, 1);
    } while (u != u0);
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    used = 0;
    dfs_ans(start - 1);
}

Compilation message (stderr)

speedrun.cpp: In function 'void dfs_init(int)':
speedrun.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < edg[v].size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
speedrun.cpp: In function 'void dfs_ans(int)':
speedrun.cpp:87:9: warning: unused variable 'cnt' [-Wunused-variable]
   87 |     int cnt = 0;
      |         ^~~

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