Submission #1290617

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290617		antonn	Speedrun (RMI21_speedrun)	C++20	100 / 100	62 ms	476 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

const int N = 1000 + 7;

int n;
vector<int> g[N];
int x[N];
vector<int> ord;

void dfs(int u, int p = 0) {
    ord.push_back(u);
    for (auto v : g[u]) {
        if (v == p) continue;
        x[v] += u;
        dfs(v, u);
    }
}

void setval(int u, int x) {
    for (int b = 0; b < 20; ++b) {
        setHint(u, b + 1, !!(x & (1 << b)));
    }
}

void assignHints(int subtask, int nn, int A[], int B[]) {
    setHintLen(20);
    n = nn;
    for (int i = 1; i < n; ++i) {
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    dfs(1);
    for (int i = 0; i + 1 < ord.size(); ++i) {
        x[ord[i]] += (ord[i + 1] << 10);
    }
    for (int i = 1; i <= n; ++i) {
        setval(i, x[i]);
    }
}

int hint[N];

int get() {
    int x = 0;
    for (int b = 0; b < 20; ++b) {
        if (getHint(b + 1)) {
            x += (1 << b);
        }
    }
    return x;
}

void speedrun(int subtask, int N, int start) {
    while (start > 1) {
        hint[start] = get();
        goTo(hint[start] & 1023);
        start = (hint[start] & 1023);
    }
    while (true) {
        hint[start] = get();
        int x = (hint[start] >> 10);
        if (x == 0) {
            break;
        }
        while (!goTo(x)) {
            hint[start] = get();
            if ((hint[start] & 1023) == 0) {
                exit(0);
            }
            start = goTo(hint[start] & 1023);
            start = (hint[start] & 1023);
        }
        goTo(x);
        start = x;
    }
}

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