Submission #1172945

#	Time	Username	Problem	Language	Result	Execution time	Memory
1172945		davele	Rarest Insects (IOI22_insects)	C++20	10 / 100	97 ms	412 KiB

insects

#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(i);
    }
    int ret = N;
    for (int i=0; i<N; i++) if (finds(i)==i) minimize (ret, sz[i]);
    return ret;
}

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