제출 #1219238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1219238		arbuzick	Speedrun (RMI21_speedrun)	C++20	100 / 100	56 ms	532 KiB

speedrun

#include "speedrun.h"

#include <bits/stdc++.h>

using namespace std;

void dfs(int v, vector<int> &ord, vector<int> &pr, vector<vector<int>> &g) {
    ord.push_back(v);
    for (auto u : g[v]) {
        if (u != pr[v]) {
            pr[u] = v;
            dfs(u, ord, pr, g);
        }
    }
}

void assignHints(int subtask, int n, int a[], int b[]) {
    vector<vector<int>> g(n);
    for (int i = 1; i < n; ++i) {
        a[i]--, b[i]--;
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    vector<int> ord, pr(n);
    dfs(0, ord, pr, g);
    setHintLen(20);
    for (int i = 0; i < (int)ord.size(); ++i) {
        for (int j = 0; j < 10; ++j) {
            setHint(ord[i] + 1, j + 1, (pr[ord[i]] >> j) & 1);
        }
        int nxt = ord[(i + 1) % n];
        for (int j = 0; j < 10; ++j) {
            setHint(ord[i] + 1, 10 + j + 1, (nxt >> j) & 1);
        }
    }
}

void speedrun(int subtask, int n, int start) {
    start--;
    int nw = start;
    set<int> used;
    while (nw != 0) {
        used.insert(nw);
        int pr = 0;
        for (int j = 0; j < 10; ++j) {
            if (getHint(j + 1)) {
                pr += (1 << j);
            }
        }
        goTo(pr + 1);
        nw = pr;
    }
    used.insert(nw);
    vector<int> st = {nw};
    while (used.size() != n) {
        int nxt = 0;
        for (int j = 0; j < 10; ++j) {
            if (getHint(10 + j + 1)) {
                nxt += (1 << j);
            }
        }
        while (!goTo(nxt + 1)) {
            st.pop_back();
            goTo(st.back() + 1);
        }
        st.push_back(nxt);
        nw = nxt;
        used.insert(nw);
    }
}

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