Submission #1191840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191840		nagorn_ph	Island Hopping (JOI24_island)	C++20	2 / 100	719 ms	1114112 KiB

island

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

using namespace std;

int aa, bb;
vector <bool> visited(305);
vector <pair <int, int>> edge;

void dfs(int u, int p){
    visited[u] = true;
    int a = query(u, 1);
    if (a == p) a = query(u, 2);
    if (visited[a] || a == aa || a == bb) return;
    // cout << u << " -> ";
    edge.emplace_back(u, a);
    dfs(a, u);
}

void line(int u, int p){
    visited[u] = true;
    int a = u;
    if (p == 1) a = bb;
    else {
        a = query(u, 1);
        if (visited[a]) a = query(u, 2);
    }
    edge.emplace_back(u, a);
    line(a, u);
}

void solve(int n, int q) {
    if (n == 3) {
        int x = query(1, 1), y = query(1, 2);
        if (x == 3 && y == 2) {
            answer(1, 3);
            answer(3, 2);
        }
        else {
            x = query(3, 1), y = query(3, 2);
            if (x == 2 && y == 1) {
                answer(1, 2);
                answer(2, 3);
            }
            else {
                answer(1, 2);
                answer(1, 3);
            }
        }
        return;
    }
    int b = query(1, 2);
    bb = query(b, 1);
    if (b != 1) {
        visited[1] = true;
        line(1, 1);
    }
    else {
        int a = query(1, 1);
        aa = a, bb = b;
        visited[1] = true;
        edge.emplace_back(1, a);
        edge.emplace_back(1, b);
        // cout << "dfs1: ";
        dfs(a, 1);
        // cout << "\n";
        // cout << "dfs2: ";
        dfs(b, 1);
        // cout << "\n";
    }
    for (auto [u, v] : edge) {
        // cout << u << " " << v << "\n";
        answer(u, v);
    }
}

• 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