Submission #1216695

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216695		Ghulam_Junaid	Speedrun (RMI21_speedrun)	C++20	100 / 100	56 ms	536 KiB

speedrun

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

const int N = 1005;
int n, len, par[N];
vector<int> g[N], path;

void give(int v, int val){
    for (int i = 0; i < len; i ++)
        setHint(v, i + 1, bool((1 << i) & val));
}

void dfs(int v, int p = 0){
    path.push_back(v);

    par[v] = p;
    for (int u : g[v])
        if (u != p)
            dfs(u, v);
}

void assignHints(int subtask, int nn, int A[], int B[]) {
    int n = nn;
    for (int i = 1; i < n; i ++){
        if (A[i] > B[i]) swap(A[i], B[i]);
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    // cout << "HERE" << endl;

    int r = 1;
    while (g[r].size() > 1) r++;
    dfs(r);

    // cout << "root = " << r << endl;

    len = 20;
    setHintLen(20);

    int ind[n + 1];
    for (int i = 0; i < path.size(); i ++)
        ind[path[i]] = i;

    for (int v = 1; v <= n; v ++){
        int nxt = 0;
        if (1 + ind[v] < path.size())
            nxt = path[1 + ind[v]];

        give(v, par[v] + 1024 * nxt);
    }
}

vector<int> extract(){
    vector<int> info;

    int val = 0;
    for (int i = 0; i < len; i ++){
        val += (1 << (i % 10)) * getHint(i + 1);
        if (i % 10 == 9){ 
            info.push_back(val);
            val = 0;
        }
    }
    return info;
}

void speedrun(int subtask, int N, int cur) {
    len = getLength();
    vector<int> vec = extract();

    while (vec[0] != 0){
        goTo(vec[0]);
        cur = vec[0];
        vec = extract();
    }

    // cout << "now at root = " << cur << endl;

    int vis = 1;
    while (vis != N){
        vec = extract();
        int nxt = vec[1];

        while (!goTo(nxt)){
            vec = extract();
            goTo(vec[0]);
        }
        vis++;
    }
}

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