Submission #764935

#	Time	Username	Problem	Language	Result	Execution time	Memory
764935		vjudge1	Speedrun (RMI21_speedrun)	C++17	63 / 100	257 ms	940 KiB

speedrun

#include "speedrun.h"
#include <vector>
#include <iostream>
#include <stack>

using namespace std;

const int MAXN = 1002;

vector<int>g[MAXN];

void setH(int pos, int val, int l, int r) {
    // cout << pos << " " << val << " " << l << " " << r << endl;
    for (int i = 0 ; i < r - l + 1 ; ++ i) {
        setHint(pos, i + l, (val >> i) & 1);
    }
}

void dfs(int v, int p) {
    // cout << v << " " << p << endl;
    setH(v, p, 1, 10);
    int child = 0;
    vector<int>children;
    for (int to : g[v]) if (to != p) {
        child = to;
        dfs(to, v);
        children.emplace_back(to);
    }
    setH(v, child, 11, 20);
    int m = children.size();
    for (int i = 0 ; i < m ; ++ i) {
        int x = children[i];
        int y = children[i == m - 1 ? 0 : i + 1];
        setH(x, y, 21, 30);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    // cout << "assignHints" << endl;
    // for every node, we want to insert:
    // 1) its parent
    // 2) its sibling
    // 3) its child
    setHintLen(30);
    for (int i = 1 ; i < N ; ++ i) {
        g[A[i]].emplace_back(B[i]);
        g[B[i]].emplace_back(A[i]);
    }
    dfs(1, 0);
    // cout << "lol" << endl;
}

int used[MAXN];

int getH(int l, int r) {
    int ret = 0;
    for (int i = 0 ; i < r - l + 1 ; ++ i) {
        ret += (1 << i) * getHint(i + l);
    }
    return ret;
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    // cout << "Speedrun" << endl;
    int x;
    while (x = getH(1, 10)) {
        // cout << x << endl;
        goTo(x);
    }
    // cout << "here " << x << endl;
    // now where are at the root
    // we can do dfs now
    used[0] = 1;
    int v = 1;
    int rep = 0;
    while (1) {
        rep++;
        // cout << "ver " << v << endl;
        used[v] = 1;
        int c = getH(11, 20);
        if (!used[c]) {
            // cout << v << " -> " << c << endl;
            goTo(c);
            v = c;
            continue;
        }
        int s = getH(21, 30);
        if (!used[s]) {
            int p = getH(1, 10);
            // cout << v << " -> " << p << " -> " << s << endl;
            goTo(p);
            goTo(s);
            v = s;
            continue;
        }
        int p = getH(1, 10);
        if (!p) break;
        // cout << v << " -----> " << p << endl;
        goTo(p);
        v = p;
    }
}

Compilation message (stderr)

speedrun.cpp: In function 'void speedrun(int, int, int)':
speedrun.cpp:66:14: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   66 |     while (x = getH(1, 10)) {
      |            ~~^~~~~~~~~~~~~

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