oj.uz

Submission #736915

# Submission time Handle Problem Language Result Execution time Memory
736915 2023-05-06T10:40:14 Z puppy Speedrun (RMI21_speedrun) C++17
100 / 100
 241 ms 936 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 700 KB Output is correct
2 Correct 145 ms 916 KB Output is correct
3 Correct 102 ms 684 KB Output is correct
4 Correct 198 ms 824 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 187 ms 672 KB Output is correct
2 Correct 192 ms 704 KB Output is correct

Subtask #3
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 840 KB Output is correct
2 Correct 239 ms 820 KB Output is correct
3 Correct 160 ms 936 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 688 KB Output is correct
2 Correct 150 ms 676 KB Output is correct
3 Correct 224 ms 796 KB Output is correct
4 Correct 167 ms 672 KB Output is correct
5 Correct 196 ms 672 KB Output is correct
6 Correct 123 ms 672 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 868 KB Output is correct
2 Correct 170 ms 676 KB Output is correct
3 Correct 181 ms 672 KB Output is correct
4 Correct 234 ms 784 KB Output is correct
5 Correct 185 ms 684 KB Output is correct
6 Correct 172 ms 680 KB Output is correct
7 Correct 170 ms 676 KB Output is correct