Submission #1239977

#	Time	Username	Problem	Language	Result	Execution time	Memory
1239977		The_Samurai	Island Hopping (JOI24_island)	C++20	2 / 100	3 ms	428 KiB

island

#include "island.h"
#include "bits/stdc++.h"
using namespace std;
#define ff first
#define ss second

struct dsu {
    vector<int> p, size;
    void init(int n) {
        p.assign(n + 1, 0);
        size.assign(n + 1, 0);
        for (int i = 0; i <= n; i++) p[i] = i;
    }

    int get(int a) {
        return p[a] == a ? a : p[a] = get(p[a]);
    }

    void merge(int a, int b) {
        a = get(a); b = get(b);
        if (a == b) return;
        if (size[a] > size[b]) swap(a, b);
        size[b] += size[a];
        p[a] = b;
    }
};

void solve(int n, int L) {
    vector<vector<int>> g(n + 1);
    dsu ds; ds.init(n + 1);
    queue<pair<int, int>> q;
    for (int i = 1; i <= n; i++) q.emplace(i, 1);
    int tot = 0;
    while (!q.empty()) {
        auto [u, i] = q.front(); q.pop();
        if (i == n) continue;
        int v = query(u, i);
        if (count(g[u].begin(), g[u].end(), v)) {
            q.emplace(u, i + 1);
            continue;
        }
        if (ds.get(u) == ds.get(v)) continue;
        tot++;
        assert(tot <= n - 1);
        ds.merge(u, v);
        g[u].emplace_back(v);
        g[v].emplace_back(u);
        q.emplace(u, i + 1);
    }
    for (int i = 1; i <= n; i++) for (int j: g[i]) {
        if (i > j) {
            // cout << i << ' ' << j << endl;
            answer(i, j);
        }
    }
}

• 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