Submission #1222081

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222081		totoro	Rarest Insects (IOI22_insects)	C++20	10 / 100	105 ms	16012 KiB

insects

#include "insects.h"

#include <vector>

int min_cardinality(int N) {
    std::vector<std::vector<int>> same(N, std::vector<int>(N));
    for (int i = 0; i < N; ++i) {
        move_inside(i);
        for (int j = i + 1; j < N; ++j) {
            move_inside(j);
            same[i][j] = same[j][i] = press_button() - 1;
            move_outside(j);
        }
        move_outside(i);
    }
    std::vector<int> color(N);
    int min = 1e9;
    for (int i = 0; i < N; ++i) {
        if (color[i]) continue;
        std::vector<int> stack = {i};
        int cursz = 0;
        while (!stack.empty()) {
            int now = stack.back();
            stack.pop_back();
            if (color[now]) continue;
            ++cursz;
            color[now] = 1;
            for (int j = 0; j < N; ++j) {
                if (same[i][j]) stack.push_back(j);
            }
        }
        min = std::min(min, cursz);
    }
    return min;
}

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