Submission #1183277

#	Time	Username	Problem	Language	Result	Execution time	Memory
1183277		madamadam3	Rarest Insects (IOI22_insects)	C++20	10 / 100	98 ms	428 KiB

insects

#include "insects.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
#define sz(x) (int) (x).size()

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;

struct DSU {
  int n;
  vi par, siz;

  DSU(int N) {
    n = N;
    par.resize(n); iota(all(par), 0);
    siz.assign(n, 1);
  }

  int find_set(int v) {
    if (par[v] == v) return v;
    return par[v] = find_set(par[v]);
  }

  void union_set(int a, int b) {
    a = find_set(a);
    b = find_set(b);

    if (a != b) {
      if (siz[a] < siz[b]) swap(a, b);
      par[b] = a;
      siz[a] += siz[b];
    }
  }
};

int min_cardinality(int N) {
  auto dsu = DSU(N);

  FOR(i, 0, N) {
    move_inside(i);
    FOR(j, 0, N) {
      // todo see if I can reduce checks where I already know that there isn't an edge between set a and set b
      if(dsu.find_set(i) == dsu.find_set(j)) continue;
      move_inside(j);
      if (press_button() > 1) {
        dsu.union_set(i, j);
      } 
      move_outside(j);
    }
    move_outside(i);
  }

  int minsz = INT_MAX;
  FOR(i, 0, N) minsz = min(minsz, dsu.siz[dsu.find_set(i)]);
  return minsz;
}

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