Submission #1256907

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256907		MisterReaper	Island Hopping (JOI24_island)	C++20	2 / 100	14 ms	508 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;
}

int ask(int v, int k) {
    assert(0 <= v && v < N && 1 <= k && k < N);
    return 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> 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;
    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 == par[v]) {
            continue;
        } else if (v != 0) {
            // check is it connected to me?
            int p = par[v];
            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]++;
            }
            if (!idx[u].contains(v) || (idx[u].contains(p) && idx[u][p] < idx[u][v])) {
                debug("leaf", v);
                stk.pop_back();
                continue;
            } 
        }

        debug(v, u);
        par[u] = v;
        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: 0 / 4
• Subtask 3: 0 / 7
• Subtask 4: 0 / 9
• Subtask 5: 0 / 13
• Subtask 6: 0 / 15
• Subtask 7: 0 / 22
• Subtask 8: 0 / 28