#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
struct DSU {
int n; vi par, siz;
DSU(int N) {
n = N;
par.resize(n); iota(par.begin(), par.end(), 0);
siz.assign(n, 1);
}
int find(int v) {
if (par[v] == v) return v;
return par[v] = find(par[v]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a != b) {
if (siz[a] < siz[b]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
}
}
};
int min_cardinality(int N) {
int n = N;
auto dsu = DSU(n);
for (int i = 0; i < n; i++) {
// if (dsu.find(i) != i) continue;
move_inside(i);
for (int j = 0; j < n; j++) {
if (i == j) continue;
move_inside(j);
if (press_button() > 1) dsu.unite(i, j);
move_outside(j);
}
move_outside(i);
}
return dsu.siz[*min_element(dsu.par.begin(), dsu.par.end(), [&](int a, int b) {
return dsu.siz[dsu.find(a)] < dsu.siz[dsu.find(b)];
})];
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |