Submission #505182

#	Time	Username	Problem	Language	Result	Execution time	Memory
505182		SanguineChameleon	Speedrun (RMI21_speedrun)	C++14	100 / 100	232 ms	808 KiB

speedrun

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

const int ms = 1e3 + 20;
vector<int> p;
vector<int> adj[ms];
bool flag[ms];
int par[ms];
int nxt[ms];

void dfs1(int u, int N, bool flag[]) {
    for (int i = 1; i <= N; i++) {
        if (getHint(i) && !flag[i]) {
            flag[i] = true;
            goTo(i);
            dfs1(i, N, flag);
            goTo(u);
        }
    }
}

void dfs5(int u) {
    p.push_back(u);
    for (auto x: adj[u]) {
        if (!flag[x]) {
            par[x] = u;
            flag[x] = true;
            dfs5(x);
        }
    }
}

void ass1(int N, int A[], int B[]) {
    setHintLen(N);
    for (int i = 1; i <= N - 1; i++) {
        setHint(A[i], B[i], 1);
        setHint(B[i], A[i], 1);
    }
}

void ass2(int N, int A[], int B[]) {
    setHintLen(20);
    int cc[N + 1];
    fill_n(cc, N + 1, 0);
    for (int i = 1; i <= N - 1; i++) {
        cc[A[i]]++;
        cc[B[i]]++;
    }
    int p = -1;
    for (int i = 1; i <= N; i++) {
        if (cc[i] > 1) {
            p = i;
            break;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < 20; j++) {
            setHint(i, j + 1, (p >> j) & 1);
        }
    }
}

void ass3(int N, int A[], int B[]) {
    setHintLen(20);
    vector<int> cc[N + 1];
    for (int i = 1; i <= N - 1; i++) {
        cc[A[i]].push_back(B[i]);
        cc[B[i]].push_back(A[i]);
    }
    int p = -1;
    for (int i = 1; i <= N; i++) {
        if ((int)cc[i].size() == 1) {
            p = i;
            break;
        }
    }
    deque<int> pt;
    bool flag[N + 1];
    fill_n(flag, N + 1, false);
    flag[p] = true;
    pt.push_back(p);
    for (int i = 1; i <= N - 1; i++) {
        for (auto x: cc[p]) {
            if (!flag[x]) {
                flag[x] = true;
                p = x;
                pt.push_back(x);
            }
        }
    }
    pt.push_front(0);
    pt.push_back(0);
    int lt, rt;
    for (int i = 1; i <= N; i++) {
        p = pt[i];
        lt = pt[i - 1];
        rt = pt[i + 1];
        for (int j = 0; j < 10; j++) {
            setHint(p, j + 1, (lt >> j) & 1);
            setHint(p, j + 11, (rt >> j) & 1);
        }
    }
}

void ass5(int N, int A[], int B[]) {
    setHintLen(20);
    for (int i = 1; i <= N - 1; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    flag[1] = true;
    dfs5(1);
    for (int i = 0; i < (int)p.size() - 1; i++) {
        nxt[p[i]] = p[i + 1];
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < 10; j++) {
            setHint(i, j + 1, (par[i] >> j) & 1);
            setHint(i, j + 11, (nxt[i] >> j) & 1);
        }
    }
}

void speed1(int N, int start) {
    bool flag[N + 1];
    fill_n(flag, N + 1, false);
    dfs1(start, N, flag);
}

void speed2(int N, int start) {
    int p = 0;
    for (int i = 0; i < 20; i++) {
        p |= (getHint(i + 1) << i);
    }
    goTo(p);
    for (int i = 1; i <= N; i++) {
        goTo(i);
        goTo(p);
    }
}

void speed3(int N, int start) {
    int lt, rt;
    while (true) {
        lt = 0;
        rt = 0;
        for (int i = 0; i < 10; i++) {
            lt |= (getHint(i + 1) << i);
            rt |= (getHint(i + 11) << i);
        }
        if (lt == 0) {
            break;
        }
        goTo(lt);
    }
    while (true) {
        lt = 0;
        rt = 0;
        for (int i = 0; i < 10; i++) {
            lt |= (getHint(i + 1) << i);
            rt |= (getHint(i + 11) << i);
        }
        if (rt == 0) {
            break;
        }
        goTo(rt);
    }
}

void speed5(int N, int start) {
    int pa, nt;
    while (true) {
        pa = 0;
        for (int i = 0; i < 10; i++) {
            pa |= (getHint(i + 1) << i);
        }
        if (pa == 0) {
            break;
        }
        goTo(pa);
    }
    while (true) {
        nt = 0;
        for (int i = 0; i < 10; i++) {
            nt |= (getHint(i + 11) << i);
        }
        if (nt == 0) {
            break;
        }
        while (true) {
            pa = 0;
            for (int i = 0; i < 10; i++) {
                pa |= (getHint(i + 1) << i);
            }
            if (!goTo(nt)) {
                goTo(pa);
            }
            else {
                break;
            }
        }
    }
}

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    if (subtask == 1) {
        ass1(N, A, B);
    }
    if (subtask == 2) {
        ass2(N, A, B);
    }
    if (subtask == 3) {
        ass3(N, A, B);
    }
    if (subtask == 4 || subtask == 5) {
        ass5(N, A, B);
    }
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    if (subtask == 1) {
        speed1(N, start);
    }
    if (subtask == 2) {
        speed2(N, start);
    }
    if (subtask == 3) {
        speed3(N, start);
    }
    if (subtask == 4 || subtask == 5) {
        speed5(N, start);
    }
}

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