제출 #1042409

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1042409		Alihan_8	Rarest Insects (IOI22_insects)	C++17	10 / 100	226 ms	596 KiB

insects

#include "insects.h"

#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define ar array
#define all(x) x.begin(), x.end()

template <class F, class S>
bool chmin(F &u, const S &v){
	bool flag = false;
	
	if ( u > v ){
		u = v; flag |= true;
	}
	
	return flag;
}

struct Dsu{
	vector <int> fa;
	
	int n;
	
	Dsu(int n) : n(n) {
		fa.resize(n);
		iota(all(fa), 0);
	}
	
	int get(int x){
		return fa[x] ^ x ? fa[x] = get(fa[x]) : x;
	}
	
	bool merge(int u, int v){
		u = get(u), v = get(v);
		
		if ( u == v ) return false;
		
		fa[v] = u;
		
		return true; 
	}
};

int min_cardinality(int n) {
	Dsu ds(n);
	
	for ( int i = 0; i + 1 < n; i++ ){
		move_inside(i);
		
		for ( int j = i + 1; j < n; j++ ){
			move_inside(j);
			
			if ( press_button() == 2 ){
				ds.merge(i, j);
			}
			
			move_outside(j);
		}
		
		move_outside(i);
	}
	
	vector <int> cnt(n);
	
	for ( int i = 0; i < n; i++ ){
		cnt[ds.get(i)]++;
	}
	
	int mn = n;
	
	for ( int i = 0; i < n; i++ ){
		if ( ds.get(i) == i ){
			chmin(mn, cnt[i]);
		}
	}
	
	return mn;
}

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