Submission #764954

#	Time	Username	Problem	Language	Result	Execution time	Memory
764954		vjudge1	Speedrun (RMI21_speedrun)	C++17	100 / 100	211 ms	804 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);
    }
}

vector<int>vec;

void dfs(int v, int p) {
    // cout << v << " " << p << endl;
    setH(v, p, 1, 10);
    vec.emplace_back(v);
    for (int to : g[v]) if (to != p) {
        dfs(to, v);
    }
}

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(20);
    for (int i = 1 ; i < N ; ++ i) {
        g[A[i]].emplace_back(B[i]);
        g[B[i]].emplace_back(A[i]);
    }
    dfs(1, 0);
    for (int i = 0 ; i < N - 1 ; ++ i) {
        int x = vec[i];
        int y = vec[i + 1];
        setH(x, y, 11, 20);
    }
    // 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;
    stack<int>s;
    s.push(v);
    while (1) {
        used[v] = 1;
        int u = getH(11, 20);
        // cout << v << " " << u << endl;
        if (!u) break;
        while (!goTo(u)) {
            s.pop();
            goTo(s.top());
        }
        s.push(u);
    }
}

Compilation message (stderr)

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

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