Submission #1236809

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236809		countless	Rarest Insects (IOI22_insects)	C++20	10 / 100	97 ms	408 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;

#define sp <<" "<<
#define endl "\n"

int min_cardinality(int N) {
    vector<int> sz(N, 1), par(N);
    iota(par.begin(), par.end(), 0);

    auto find = [&](auto &&find, int u) -> int {
        if (u == par[u]) return u;
        return par[u] = find(find, par[u]);
    };

    auto unite = [&](int u, int v) -> void {
        u = find(find, u), v = find(find, v);
        if (u == v) return;
        if (sz[u] < sz[v]) swap(u, v);
        par[v] = u;
        sz[u] += sz[v];
    };

    for (int i = 0; i < N; i++) {
        move_inside(i);
        for (int j = i+1; j < N; j++) {
            move_inside(j);
            int res = press_button();
            if (res == 2) {
                unite(i, j);
            }
            move_outside(j);
        }
        move_outside(i);
    }

    int ans = INT_MAX;
    for (int i = 0; i < N; i++) {
        ans = min(ans, sz[find(find, i)]);
    }

    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 75