제출 #629748

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629748		cjoa	드문 곤충 (IOI22_insects)	C++17	10 / 100	350 ms	316 KiB

insects

#include "insects.h"

#include <vector>
#include <random>
#include <algorithm>
#include <numeric>

#include <cassert>

using namespace std;

#define SZ(x) int((x).size())

mt19937 gen(123);

class DisjointSet {
   int N;
   int ncomp;
   vector<int> par;
   vector<int> sz;

public:
   DisjointSet(size_t _N) : N(_N), ncomp(_N), par(_N, -1), sz(_N, 1) {}
   int num_comp() const {
      return ncomp;
   }
   int size(int u) {
      return sz[ find_rep(u) ];
   }
   int find_rep(int u) {
      return par[u] < 0 ? u : par[u] = find_rep(par[u]);
   }
   bool union_rep(int u, int v) {
      int u_root = find_rep(u);
      int v_root = find_rep(v);
      if (u_root == v_root)
         return false;
      if (sz[u_root] < sz[v_root])
         swap(u_root, v_root);
      par[v_root] = u_root;
      sz[u_root] += sz[v_root];
      --ncomp;
      return true;
   }
};


int min_cardinality(int N) {
   vector<int> order(N);
   iota(order.begin(), order.end(), 0);
   std::shuffle(order.begin(), order.end(), gen);

   vector<int> distinct;
   DisjointSet dset(N);
   for (int i : order) {
      move_inside(i);
      if (!distinct.empty() and press_button() == 2) {
         std::shuffle(distinct.begin(), distinct.end(), gen);
         for (int k = SZ(distinct)-1; k >= 0; --k) {
            int& j = distinct[k];
            move_outside(j);
            if (press_button() == 1) {
               dset.union_rep(i, j);
               j = i;
               break;
            }
            move_inside(j);
         }
      }
      else {
         distinct.push_back(i);
      }
   }

   int ret = N;
   for (int i = 0; i < N; ++i)
      ret = min(ret, dset.size(i));

   return ret;
}

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