oj.uz

Submission #736905

# Submission time Handle Problem Language Result Execution time Memory
736905 2023-05-06T10:37:04 Z puppy Speedrun (RMI21_speedrun) C++17
0 / 100
 234 ms 800 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) {
        goTo(par());
        cur = par();
    }
    int mmr = -1;
    while (1) {
        //cur의 자식을 일단 모두 방문
        //chd_cnt번째 자식 방문할 차례
        if (chd_cnt[cur] == 0) {
            int nxt = chd();
            bool suc = nxt ? goTo(nxt) : 0;
            if (suc) {
                chd_cnt[cur]++;
                cur = nxt;
                continue;
            }
            else {
                mmr = nxt;
                if (par() == 0) return;
                else {
                    cur = par();
                    assert(goTo(par()));
                }
            }
        }
        else {
            assert(mmr != -1);
            if (goTo(mmr)) {
                cur = mmr;
                continue;
            }
            else {
                if (par() == 0) return;
                else {
                    cur = par();
                    assert(goTo(par()));
                }
            }
        }
    }
    //자식
}

Subtask #1
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 204 ms 568 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 223 ms 544 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 185 ms 800 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 234 ms 748 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 226 ms 676 KB Invalid node index to goTo
2 Halted 0 ms 0 KB -