Submission #1074387

#	Time	Username	Problem	Language	Result	Execution time	Memory
1074387		Zicrus	Rarest Insects (IOI22_insects)	C++17	10 / 100	162 ms	448 KiB

insects

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

typedef long long ll;

int n;
vector<int> lnk, sz;

int find(int a) {
    if (lnk[a] != a) return lnk[a] = find(lnk[a]);
    return lnk[a];
}

void unite(int a, int b) {
    a = find(a); b = find(b);
    if (a == b) return;
    lnk[a] = b;
    sz[b] += sz[a];
}

int min_cardinality(int N) {
    n = N;
    lnk = vector<int>(n);
    sz = vector<int>(n, 1);
    for (int i = 0; i < n; i++) lnk[i] = i;

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

    int mn = n;
    for (int i = 0; i < n; i++) {
        if (i != lnk[i]) continue;
        mn = min(mn, sz[i]);
    }
    return mn;
}

#ifdef TEST
#include "grader.cpp"
#endif

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