Submission #1168812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168812		SmuggingSpun	Rarest Insects (IOI22_insects)	C++20	10 / 100	98 ms	420 KiB

insects

#include<bits/stdc++.h>
#include "insects.h"
using namespace std;
template<class T>void minimize(T& a, T b){
    if(a > b){
        a = b;
    }
}
int min_cardinality(int n){
    vector<int>parent(n), size(n);
    iota(parent.begin(), parent.end(), 0);
    fill(size.begin(), size.end(), 1);
    auto find_set = [&] (int N){
        while(N != parent[N]){
            N = parent[N] = parent[parent[N]];
        }
        return N;
    };
    auto merge = [&] (int u, int v){
        if((u = find_set(u)) != (v = find_set(v))){
            if(size[u] < size[v]){
                swap(u, v);
            }
            size[parent[v] = u] += size[v];
        }
    };
    vector<int>S;
    for(int i = 0; i < n; i++){
        move_inside(i);
        S.emplace_back(i);
        if(press_button() == 2){
            S.pop_back();
            vector<int>remove;
            int x;
            while(true){
                x = S.back();
                S.pop_back();
                move_outside(x);
                if(press_button() == 1){
                    break;
                }
                remove.emplace_back(x);
            }
            merge(i, x);
            for(int& j : remove){
                S.emplace_back(j);
                move_inside(j);
            }
            S.emplace_back(i);
        }
    }
    int ans = n;
    for(int i = 0; i < n; i++){
        minimize(ans, size[find_set(i)]);
    }
    return ans;
}

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