# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858700 | imarn | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#include "insects.h"
#define f first
#define s second
#define ll long long
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
//#define sz(x) (ll)x.size()
#define all(x) x.begin(),x.end()
using namespace std;
int pr[2001]{0};
int sz[2001]{0};
int get(int r){
return pr[r]==r?r:pr[r]=get(pr[r]);
}
int min_cardinality(int N)
{
iota(pr,pr+N+1,0);
for(int i=0;i<N+1;i++)sz[i]=1;
for(int i=0;i<N;i++){
for(int j=i+1;j<N;j++){
move_inside(i);
move_inside(j);
int u=get(i);
int v=get(j);
if(get(u)==get(v))continue;
if(press_button()==2&&u!=v{
sz[u]+=sz[v];
pr[v]=get(u);
}move_outside(i);
move_outside(j);
}
}int ans=1e9;
for(int i=0;i<N;i++)ans=min(ans,sz[get(i)]);
return ans;
}