Submission #1064134

#	Time	Username	Problem	Language	Result	Execution time	Memory
1064134		MarwenElarbi	Rarest Insects (IOI22_insects)	C++17	10 / 100	215 ms	16936 KiB

insects

#include <bits/stdc++.h>
#include "insects.h"
using namespace std;
#define pb push_back
#define ll long long
#define fi first
#define se second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int nax=5005;
int parent[nax];
int sz[nax];
int find(int x){
  if(parent[x]==x) return x;
  return parent[x]=find(parent[x]);
}
bool sameset(int x,int y){
  return find(x)==find(y);
}
void joinset(int x,int y){
  x=find(x);
  y=find(y);
  parent[x]=y;
  sz[y]+=sz[x];
  return; 
}
int min_cardinality(int N) {
  vector<pair<int,int>> tab;
  for (int i = 0; i < N; ++i)
  {
    parent[i]=i;
    sz[i]=1;
  }
  for (int i = 0; i < N; ++i)
  {
    for (int j = i+1; j < N; ++j)
    {
        tab.pb({i,j});
    }
  }
  int cnt=0;
  shuffle(tab.begin(),tab.end(),rng);
  for (int i = 0; i < min(N*(N-1)/2,20000); ++i)
  {
    if(sameset(tab[i].fi,tab[i].se)) continue;
    cnt++;
    move_inside(tab[i].fi);
    move_inside(tab[i].se);
    int a=press_button();
    move_outside(tab[i].fi);
    move_outside(tab[i].se);
    if(a==2) joinset(tab[i].fi,tab[i].se);
  }
  int mn=1e9;
  for (int i = 0; i < N; ++i)
  {
    mn=min(mn,sz[find(i)]);
  }
  return mn;
}

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