Submission #538336

#	Time	Username	Problem	Language	Result	Execution time	Memory
538336		joelau	Speedrun (RMI21_speedrun)	C++14	100 / 100	111 ms	884 KiB

speedrun

#include "speedrun.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<int> lst[1005], pre;

void dfs (int x, int p) {
    for (int i = 0; i < 10; ++i) if (p & (1<<i)) setHint(x,i+1,1);
    pre.push_back(x);
    for (int v: lst[x]) if (v != p) dfs(v,x);
}

void assignHints(int subtask, int N, int A[], int B[]) {
    for (int i = 1; i < N; ++i) {
        lst[A[i]].push_back(B[i]);
        lst[B[i]].push_back(A[i]);
    }
    setHintLen(20);
    dfs(1,1);
    for (int i = 0; i < N-1; ++i) for (int j = 0; j < 10; ++j) if (pre[i+1] & (1<<j)) setHint(pre[i],j+11,1);
}

int getA() {
    int ans = 0;
    for (int i = 0; i < 10; ++i) if (getHint(i+1)) ans |= (1<<i);
    return ans;
}

int getB() {
    int ans = 0;
    for (int i = 0; i < 10; ++i) if (getHint(i+11)) ans |= (1<<i);
    return ans;
}

void speedrun(int subtask, int N, int start) {
    int n = start, a = getA();
    while (n != a) {
        goTo(a), n = a, a = getA();
    }
    int b = getB();
    for (int i = 0; i < N-1; ++i) {
        while (!goTo(b)) goTo(a), n = a, a = getA();
        n = b, a = getA(), b = getB();
    }
}

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