Submission #1230426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230426		madamadam3	Rarest Insects (IOI22_insects)	C++20	10 / 100	99 ms	412 KiB

insects

#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 = i+1; j < n; j++) {
      if (dsu.find(j) != 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)];
  })];
}

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