Submission #1256981

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256981		MisterReaper	Island Hopping (JOI24_island)	C++20	65 / 100	4 ms	532 KiB

island

#include <bits/stdc++.h>
#include "island.h"

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

namespace {
    int N;
}

std::map<std::pair<int, int>, int> save;

int ask(int v, int k) {
    assert(0 <= v && v < N && 1 <= k && k < N);
    if (save.contains({v, k})) {
        return save[{v, k}];
    }
    return save[{v, k}] = query(v + 1, k) - 1;
}

void solve(int N, int L) {
    ::N = N;
    // int variable_example = query(1, 1);
    // for (int i = 2; i <= N; i++) {
    //     answer(1, i);
    // }

    std::vector<int> vis(N), lst(N, -1);
    std::vector<int> cur(N, 1), par(N, -1);
    std::vector<std::map<int, int>> idx(N);
    std::vector<int> stk {0};
    std::vector<std::pair<int, int>> ans;
    vis[0] = true;
    while (ans.size() != N - 1) {
        int v = stk.back();
        debug(stk);
        if (cur[v] == N) {
            stk.pop_back();
            continue;
        }

        debug(v, cur[v]);
        int u = ask(v, cur[v]);
        idx[v][u] = cur[v];
        cur[v]++;
        debug(u);

        if (u < lst[v]) {
            stk.pop_back();
            continue;
        } else if (vis[u]) {
            if (u == par[v]) {
                continue;
            } else {
                debug("pop", v);
                stk.pop_back();
                continue;
            }
        } else if (v != 0) {
            // check is it connected to me?
            int p = par[v], stp = cur[u];
            while (!idx[u].contains(p) && !idx[u].contains(v)) {
                int x = ask(u, cur[u]);
                debug(u, cur[u], x);
                idx[u][x] = cur[u];
                cur[u]++;
            }
            cur[u] = stp;
            if (idx[u].contains(v) && idx[u].contains(p)) {
                if (idx[u][p] < idx[u][v]) {
                    debug("leaf", v);
                    stk.pop_back();
                    continue;
                }
            } else if (idx[u].contains(p)) {
                debug("leaf", v);
                stk.pop_back();
                continue;
            }
        }

        debug(v, u);
        vis[u] = true;
        par[u] = v;
        lst[v] = u;
        ans.emplace_back(v, u);
        stk.emplace_back(u);
    }

    for (auto[u, v] : ans) {
        answer(u + 1, v + 1);
    }
}

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 0 / 7
• Subtask 4: 9 / 9
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 22 / 22
• Subtask 8: 0 / 28