Submission #726215

#	Time	Username	Problem	Language	Result	Execution time	Memory
726215		ismayil	Rarest Insects (IOI22_insects)	C++17	10 / 100	229 ms	256 KiB

insects

#pragma GCC optimize("O3")
#include "insects.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 2001;
int par[MAX];
int find(int u){
	if(par[u] < 0) return u;
	return par[u] = find(par[u]);
}
bool unite(int u, int v){
	u = find(u), v = find(v);
	if(u == v) return false;
	if(par[u] > par[v]) swap(u, v);
	par[u] += par[v];
	par[v] = u;
	return true;
}
int min_cardinality(int N) {
	memset(par, -1, sizeof(par));
	for(int i = 0; i < N; i++){
		for(int j = i + 1; j < N; j++){
			move_inside(i);
			move_inside(j);
			if(press_button() == 2) unite(i, j);
			move_outside(i);
			move_outside(j);
		}
	}
	int ans = N + 1;
	for(int i = 0; i < N; i++){
		ans = min(ans, -par[find(i)]);
	}
	return ans;
}

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