Submission #1231207

#	Time	Username	Problem	Language	Result	Execution time	Memory
1231207		madamadam3	Rarest Insects (IOI22_insects)	C++20	10 / 100	96 ms	448 KiB

insects

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

using namespace std;

#define FOR(i, a, b) for (int i = a; i < b; i++)
using vi = vector<int>;

struct DSU {
  int n; vi par, siz;

  DSU() {};
  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 n;
DSU dsu;

set<int> dac(int l, int r) {
  if (l + 1 == r) return set<int>({l});

  int m = l + (r - l) / 2;
  set<int> left = dac(l, m), right = dac(m, r);
  
  for (auto &el : left) {
    move_inside(el);

    for (auto &rel : right) {
      move_inside(rel);
      int press_ans = press_button();
      move_outside(rel);

      if (press_ans > 1) {
        dsu.unite(el, rel);
      }
    }

    move_outside(el);
  }

  set<int> ans;
  for (auto &el : left) ans.insert(dsu.find(el));
  for (auto &el : right) ans.insert(dsu.find(el));
  return ans;
}

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

  dac(0, n);

  int ans = n;
  for (int i = 0; i < n; i++) {
      if (dsu.par[i] != i) continue;
      ans = min(ans, dsu.siz[i]);
  }
  return ans;
}

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