Submission #1203790

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203790		LucaIlie	Island Hopping (JOI24_island)	C++20	2 / 100	2 ms	432 KiB

island

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

using namespace std;

const int MAX_N = 300;
bool isEdge[MAX_N + 1][MAX_N + 1];
int parent[MAX_N + 1];
int comp;

int findParent(int x) {
    if (parent[x] == x)
        return x;
    parent[x] = findParent(parent[x]);
    return parent[x];
}

bool connected(int u, int v) {
    return findParent(u) == findParent(v);
}   

void connect(int u, int v) {
    u = findParent(u);
    v = findParent(v);
    if (u == v)
        return;
    comp--;
    parent[u] = v;
}

void solve(int n, int l) {
    vector<int> cand;
    for (int i = 1; i <= n; i++) {
        cand.push_back(i);
        parent[i] = i;
    }

    int round = 1;
    comp = n;
    while (round < n && comp > 1 && !cand.empty()) {
        vector<int> newCand;
        for (int u: cand) {
            int v = query(u, round);
            // if (!isEdge[u][v] && connected(u, v))
                // continue;
            if (!connected(u, v))
                isEdge[u][v] = isEdge[v][u] = true;
            connect(u, v);
            newCand.push_back(v);
        }
        round++;
    }

    for (int u = 1; u <= n; u++) {
        for (int v = u + 1; v <= n; v++) {
            if (isEdge[u][v]) {
                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