Submission #736899

#	Time	Username	Problem	Language	Result	Execution time	Memory
736899		puppy	Speedrun (RMI21_speedrun)	C++17	0 / 100	220 ms	816 KiB

speedrun

#include "speedrun.h"
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
using namespace std;

void assignHints(int subtask, int N, int A[], int B[]) { /* your solution here */
    setHintLen(20);
    vector<vector<int>> adj(N+1), g(N+1);
    for (int i = 1; i < N; i++) {
        adj[A[i]].push_back(B[i]);
        adj[B[i]].push_back(A[i]);
    }
    int last_leaf = -1;
    function<void(int, int)> settree = [&](int v, int p)
    {
        g[p].push_back(v);
        for (int i:adj[v]) {
            if (i != p) settree(i, v);
        }
    };
    settree(1, 0);
    //앞 10개에 부모의 정보 저장
    function<void(int, int)> dfs = [&](int v, int p)
    {
        for (int i = 0; i < 10; i++) {
            setHint(v, i + 1, (p >> i) & 1);
        }
        if (g[v].empty()) {
            last_leaf = v;
            return;
        }
        for (int i = 10; i < 20; i++) {
            setHint(v, i + 1, (g[v][0] >> (i - 10)) & 1);
        }
        for (int i = 0; i < (int)g[v].size(); i++) {
            if (i >= 1) {
                //g[v][i]를 last_leaf에 부여
                assert(last_leaf != -1);
                for (int k = 10; k < 20; k++) {
                    setHint(last_leaf, k + 1, (g[v][i] >> (k - 10)) & 1);
                }
            }
            dfs(g[v][i], v);
        }
    };
    dfs(1, 0);
}

void speedrun(int subtask, int N, int start) { /* your solution here */
    //start
    //자식 방문하기
    function<int()> par = [&]()
    {
        int ret = 0;
        for (int i = 9; i >= 0; i--) {
            ret <<= 1;
            ret += getHint(i + 1);
        }
        return ret;
    };
    function<int()> chd = [&]()
    {
        int ret = 0;
        for (int i = 19; i >= 10; i--) {
            ret <<= 1;
            ret += getHint(i + 1);
        }
        return ret;
    };
    vector<int> chd_cnt(N+1);
    int cur = start;
    while (cur != 1) {
        goTo(par());
        cur = par();
    }
    int mmr = -1;
    while (1) {
        //cur의 자식을 일단 모두 방문
        //chd_cnt번째 자식 방문할 차례
        if (chd_cnt[cur] == 0) {
            bool suc = goTo(chd());
            if (suc) {
                chd_cnt[cur]++;
                cur = chd();
                continue;
            }
            else {
                mmr = chd();
                if (par() == 0) return;
                else {
                    cur = par();
                    goTo(par());
                }
            }
        }
        else {
            assert(mmr != -1);
            if (goTo(mmr)) {
                cur = mmr;
                continue;
            }
            else {
                if (par() == 0) return;
                else {
                    cur = par();
                    goTo(par());
                }
            }
        }
    }
    //자식
}

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