Submission #1127071

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127071		not_amir	Speedrun (RMI21_speedrun)	C++20	100 / 100	90 ms	468 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;

vector<int> ord;
vector<int> parent;

void dfs(int v, int p) {
    ord.push_back(v);
    parent[v] = p;
    for (int u : G[v]) {
        if (u == p) continue;
        dfs(u, v);
    }
}

void setHint(int v, int x, int s, int l) {
    for (int i = 0; i < l; i++)
        setHint(v, s + i + 1, (x >> i) & 1);
}

void assignHints(int subtask, int N, int A[], int B[]) {
    G.assign(N + 1, vector<int>());
    for (int i = 1; i < N;i ++)
        G[A[i]].push_back(B[i]), G[B[i]].push_back(A[i]);
    ord.reserve(N);
    parent.assign(N + 1, 0);
    dfs(1, 0);
    setHintLen(20);
    for (int i = 1; i <= N; i++)
        setHint(i, parent[i], 0, 10);
    for (int i = 0; i < N; i++)
        setHint(ord[i], ord[(i + 1) % N], 10, 10);
}

int getHint(int v, int s, int l) {
    int ans = 0;
    for (int i = 0; i < l; i++)
        ans |= getHint(s + i + 1) << i;
    return ans;
}

void speedrun(int subtask, int N, int start) {
    int v = start;
    while (true) {
        int jmp = getHint(v, 10, 10);
        while (!goTo(jmp))
            goTo(getHint(v, 0, 10));
        v = jmp;
        if (v == start)
            break;
    }
}

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