# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
858700 | 2023-10-09T04:58:56 Z | imarn | Rarest Insects (IOI22_insects) | C++17 | 0 ms | 0 KB |
#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; }