Submission #835546

#	Time	Username	Problem	Language	Result	Execution time	Memory
835546		ma_moutahid	Rarest Insects (IOI22_insects)	C++17	10 / 100	315 ms	304 KiB

insects

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

using namespace std;

#define vi vector<int>

vi d;
int parent (int x){
  if(d[x]==x)return x;
  else return d[x]=parent(d[x]);
}
void connect(int x, int y){
  d[parent(x)]=parent(y);
}
int min_cardinality(int N) {
  int n=N;
  d.resize(n);
  map<int,int>m;
  for(int i=0;i<n;i++){
    d[i]=i;
  }
  vi found(n);
  for(int i=0;i<n-1;i++){
    if(found[i])continue;
    move_inside(i);
    for(int j=i+1;j<n;j++){
      if(found[j])continue;
      move_inside(j);
      if(press_button()==2){connect(i,j);found[j]=1;}
      move_outside(j);
    }
    move_outside(i);
  }
  for(int i=0;i<n;i++){
    m[parent(i)]++;
  }
  int mn= 1e9;
  for(auto p:m){
    mn=min(mn,p.second);
  }
  return mn;
}

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