Submission #537112

#	Time	Username	Problem	Language	Result	Execution time	Memory
537112		siewjh	Speedrun (RMI21_speedrun)	C++17	100 / 100	117 ms	840 KiB

speedrun

#include "speedrun.h"
#include <vector>
using namespace std;
const int MAXN = 1005;
vector<int> adjlist[MAXN];
int p[MAXN], tour[MAXN];
int ind = 0;
void dfs(int x, int par){
    p[x] = par; tour[ind++] = x;
    for (int nxt : adjlist[x]){
        if (nxt == par) continue;
        dfs(nxt, x);
    }
}

void assignHints(int subtask, int N, int A[], int B[]) {
    setHintLen(20);
    for (int i = 1; i < N; i++){
        int x = A[i], y = B[i];
        adjlist[x].push_back(y);
        adjlist[y].push_back(x);
    }
    dfs(1, -1);
    for (int i = 2; i <= N; i++)
        for (int k = 0; k <= 9; k++)
            if (p[i] & (1 << k))
                setHint(i, k + 1, 1);
    for (int i = 0; i < N; i++)
        for (int k = 0; k <= 9; k++)
            if (tour[(i + 1) % N] & (1 << k))
                setHint(tour[i], k + 11, 1);
}

void speedrun(int subtask, int N, int start) {
    int curr = start;
    do{
        int nxt = 0;
        for (int k = 0; k <= 9; k++)
            if (getHint(k + 11))
                nxt += (1 << k);
        while (!goTo(nxt)){
            int par = 0;
            for (int k = 0; k <= 9; k++)
                if (getHint(k + 1))
                    par += (1 << k);
            curr = par;
            goTo(par);
        }
        curr = nxt;
    } while (curr != start);
}

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