# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1172943 | davele | Rarest Insects (IOI22_insects) | C++20 | 0 ms | 0 KiB |
#ifndef davele
#include "insects.h"
#endif // davele
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;
//const int mod = ;
//void add (int &a, const int&b){
// a+=b;
// if (a>=mod) a-=mod;
//}
//
//void sub (int&a, const int&b){
// a-=b;
// if (a<0) a+=mod;
//}
//
//void mul (int&a, const int&b){
// a*=b;
// a%=mod;
//}
template<class X, class Y>
bool minimize(X &x, const Y&y){
if (x<=y) return false;
else{
x = y;
return true;
}
}
template<class X, class Y>
bool maximize (X &x, const Y&y){
if (x>=y) return false;
else{
x = y;
return true;
}
}
////////////////////////////////////////////////////////////////////////////
const int lim = 2e3, limit = lim+5;
int par[limit], n, sz[limit];
int finds (int u){
if (u==par[u]) return u;
return par[u] = finds (par[u]);
}
bool unions (int u, int v){
int a = finds (u), b = finds (v);
if (a==b) return false;
if (sz[a]<sz[b]) swap(a, b);
sz[a]+=sz[b];
par[b] = a;
return true;
}
void make_set(){
for (int i=0; i<n; i++){
par[i] = i;
sz[i] = 1;
}
}
int min_cardinality(int N){
n = N;
make_set();
for (int i=0; i<n; i++){
move_inside(i);
for (int j=i+1; j<n; j++){
move_inside(j);
if (press_button()==2) unions(i, j);
move_outside(j);
}
move_outside(j);
}
int ret = N;
for (int i=0; i<N; i++) if (finds(i)==i) minimize (ret, sz[i]);
return ret;
}