제출 #1089008

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1089008		Alihan_8	게임 (IOI14_game)	C++17	42 / 100	1048 ms	8084 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

const int N = 1505;

int is[N][N];

struct dsu{
	int fa[N];
	
	vector <vector<int>> c;
	
	dsu(){
		c.resize(N);
		
		for ( int i = 0; i < N; i++ ){
			fa[i] = i;
			c[i].push_back(i);
		}
	}
	
	int get(int u){
		return fa[u] ^ u ? fa[u] = get(fa[u]) : u;
	}
	
	int merge(int u, int v){
		u = get(u), v = get(v);
		
		//~ assert(u != v);
		
		if ( c[u].size() < c[v].size() ) swap(u, v);
		
		int cnt = c[u].size() * c[v].size();
		
		for ( auto &x: c[u] ){
			for ( auto &y: c[v] ){
				cnt -= is[x][y];
			}
		}
		
		if ( cnt == 0 ){
			for ( auto &y: c[v] ){
				c[u].push_back(y);
				fa[y] = u;
			} c[v].clear();
			
			return 1;
		}
		
		return 0;
	}
} ds;

void initialize(int N) {
	
}

int hasEdge(int u, int v) {
	is[u][v] = is[v][u] = 1;
	
	return ds.merge(u, v);
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 0 / 58