Submission #1053698

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053698		Ignut	Rarest Insects (IOI22_insects)	C++17	10 / 100	226 ms	344 KiB

insects

/* Ignut
started: 11.08.2024
now: 11.08.2024
████████████████████████████████████████████████████████████████████
████████████████████████████████    ████████████████████████████████
██████████████████████████████        ██████████████████████████████
██████      ██████████████████        ██████████████████      ██████
██████          ██████████████        ██████████████          ██████
██████      ██    ████████████        ████████████    ██      ██████
██████      ████    ██████████        ██████████    ████      ██████
██████      ████      ██████████    ██████████      ████      ██████
██████      ████      ██████████    ██████████    ██████      ██████
██████      ██████    ██████████    ██████████    ██████      ██████
██████      ██████    ████████        ████████    ██████      ██████
██████      ██████      ██████        ██████      ██████      ██████
██████      ████        ████            ████        ████      ██████
██████            ██████████    ████    ██████████            ██████
██████      ██      ██████    ████████    ██████      ██      ██████
██████      ██████            ████████            ██████      ██████
██████                    ██            ██                    ██████
██████████████████████      ████    ████      ██████████████████████
████████████████████████      ██    ██      ████████████████████████
██████████████████████████                ██████████████████████████
██████████████████████████████        ██████████████████████████████
████████████████████████████████████████████████████████████████████
*/

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void move_inside(int i);
void move_outside(int i);
int press_button();

struct DSU {
    vector<int> p, sz;
    void Init(int n) {
        p.assign(n, 0);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }
    int Get(int v) {
        return p[v] == v ? v : p[v] = Get(p[v]);
    }
    void Unite(int u, int v) {
        u = Get(u), v = Get(v);
        if (u == v) return;
        if (sz[u] > sz[v]) swap(u, v);
        sz[v] += sz[u];
        p[u] = v;
    }
};

int min_cardinality(int N) {
    DSU dsu; dsu.Init(N);
    for (int i = 0; i < N; i ++) {
        move_inside(i);
        for (int j = i + 1; j < N; j ++) {
            move_inside(j);
            if (press_button() == 2) {
                dsu.Unite(i, j);
            }
            move_outside(j);
        }
        move_outside(i);
    }
    int res = N;
    for (int i = 0; i < N; i ++) res = min(res, dsu.sz[dsu.Get(i)]);
    return res;
}

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