Submission #658590

#	Time	Username	Problem	Language	Result	Execution time	Memory
658590		pere_gil	Rarest Insects (IOI22_insects)	C++17	10 / 100	367 ms	300 KiB

insects

#include "insects.h"
#include "bits/stdc++.h"
using namespace std;

const int MAX_N=2005;
int p[MAX_N],ele[MAX_N];

int find_set(int n){
	return (p[n]==n) ? n : p[n]=find_set(p[n]);
}
bool same_set(int a, int b){
	return find_set(a)==find_set(b);
}
void union_set(int a, int b){
	a=find_set(a),b=find_set(b);
	if(a==b) return;
	ele[a]+=ele[b];
	p[b]=a;
}

int min_cardinality(int n) {
	iota(p,p+MAX_N,0);
	for(int i=0;i<n;i++) ele[i]=1;
	
	for(int i=0;i<n;i++){
		move_inside(i);
		for(int j=i+1;j<n;j++){
			if(same_set(i,j)) continue;
			move_inside(j);
			if(press_button()==2) union_set(i,j);
			move_outside(j);
		}
		move_outside(i);
	}

	int res=1e9;
	for(int i=0;i<n;i++)
		res=min(res,ele[find_set(i)]);
	return res;
}

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