Submission #1242047

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242047		sano	Rarest Insects (IOI22_insects)	C++20	10 / 100	100 ms	868 KiB

insects

#include "insects.h"
#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<long double, long double>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

vec<int> original_pole;

set<int> masina;
/*
void move_inside(int x) {
    masina.insert(x);
    return;
}

void move_outside(int x) {
    masina.erase(x);
    return;
}

int press_button() {
    unordered_map<int, int> umap;
    int maxi = 0;
    for (auto i : masina) {
        umap[original_pole[i]]++;
        maxi = max(maxi, umap[original_pole[i]]);
    }
    return maxi;
}
*/
int dfs(int x, vec<int>& bol, vec<vec<int>>&g) {
    bol[x] = 1;
    int poc = 1;
    for (auto i : g[x]) {
        if (bol[i]) continue;
        poc += dfs(i, bol, g);
    }
    return poc;
}

int min_cardinality(int n) {
    vec<vec<int>> g(n);
    For(i, n) {
        move_inside(i);
        ffor(j, i + 1, n) {
            move_inside(j);
            int x = press_button();
            if (x == 2) {
                g[i].push_back(j);
                g[j].push_back(i);
            }
            move_outside(j);
        }
        move_outside(i);
    }
    vec<int> bol(n, 0);
    int mini = n;
    For(i, n) {
        if (bol[i]) continue;
        mini = min(mini, dfs(i, bol, g));
    }
    return mini;
}

/*
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n; cin >> n;
    vec<int> p(n);
    For(i, n) cin >> p[i];
    original_pole = p;
    cout << min_cardinality(n) << '\n';
    return 0;
}
*/

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