제출 #1240208

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1240208		rythm_of_knight	Island Hopping (JOI24_island)	C++17	100 / 100	3 ms	776 KiB

island

#include "island.h"
#include <bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ar array
using namespace std;
typedef long long ll;

const int N = 303;

int a[N][N], vis[N], f[N], sz[N], add[N];

int father(int x) {
    if (f[x] != f[f[x]])
        return f[x] = father(f[x]);
    return f[x];
}

void dsu(int u, int v) {
    u = father(u), v = father(v);
    if (u == v)
        return;
    if (sz[u] < sz[v])
        swap(u, v);
    sz[u] += sz[v];
    f[v] = u;
}

void solve(int n, int l) {
    for (int i = 1; i <= n; i++)
        f[i] = i, sz[i] = 1;
    int k = 1, cnt = 1;
    while (cnt < n) {
        int x = query(1, k);
        // cout << x << ' ' << flush;
        if (father(1) == father(x)) {
            k++;
            continue;
        }
        int t = 1, y, f = -1, c = -1;
        do {
            y = query(x, t);
            c++;
            if (f == -1)
                f = y;
            dsu(x, y);
            a[x][y] = a[y][x] = 1, cnt++, t++;
        } while (father(y) != father(1));
        k++;
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
            if (a[i][j])
                answer(i, j);
}

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