Submission #736915

#	Time	Username	Problem	Language	Result	Execution time	Memory
736915		puppy	Speedrun (RMI21_speedrun)	C++17	100 / 100	241 ms	936 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) {
        int nxt = par();
        assert(1 <= nxt && nxt <= N);
        goTo(nxt);
        cur = nxt;
    }
    int mmr = -1;
    while (1) {
        //cur의 자식을 일단 모두 방문
        //chd_cnt번째 자식 방문할 차례
        if (chd_cnt[cur] == 0) {
            int nxt = chd();
            bool suc = false;
            if (nxt) {
                suc = goTo(nxt);
                assert(1 <= nxt && nxt <= N);
            }
            if (suc) {
                chd_cnt[cur]++;
                cur = nxt;
                continue;
            }
            else {
                mmr = nxt;
                if (par() == 0) return;
                else {
                    cur = par();
                    assert(1 <= par() && par() <= N);
                    assert(goTo(par()));
                }
            }
        }
        else {
            assert(mmr != -1);
            bool suc = (1 <= mmr && mmr <= N) ? goTo(mmr) : false;
            if (suc) {
                cur = mmr;
                continue;
            }
            else {
                if (par() == 0) return;
                else {
                    cur = par();
                    assert(1 <= par() && par() <= N);
                    assert(goTo(par()));
                }
            }
        }
    }
    //자식
}

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