제출 #1176699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1176699		fabijan_cikac	게임 (IOI14_game)	C++20	0 / 100	0 ms	328 KiB

game

#include <bits/stdc++.h>

using namespace std;

#define pb push_back

const int MAXN = 21;

int N; int dsu[MAXN];
int e[MAXN][MAXN];

void initialize(int n){
	memset(e, -1, sizeof(e)); N = n;
	for (int i = 0; i < n; ++i) dsu[i] = i;
}

int parent(int x){
	return dsu[x] == x ? x : dsu[x] = parent(dsu[x]);
}

void merge(int x, int y){
	dsu[x] = parent(x);
	dsu[y] = parent(y);
	if (dsu[x] != dsu[y]) dsu[y] = x;
}

//exist bad partition
bool bad(int X){
	vector<int> a, b;
	for (int i = 0; i < N; ++i){
		if (parent(i) == X) a.pb(i);
		else b.pb(i);
	}
	
	bool B = 1;
	for (int x: a)
		for (int y: b)
			if (e[x][y] != 0) B = 0;
	return B;
}

int hasEdge(int x, int y){
	e[x][y] = 0, e[y][x] = 0;
	if (bad(parent(x)) || bad(parent(y))){
		e[x][y] = 1, e[y][x] = 1;
		merge(x, y);
	}
	
	//cout << x << ' ' << y << " -> " << e[x][y] << endl;
	return e[x][y];
}

/*int main(){
	initialize(4);
	
	hasEdge(0, 3);
	hasEdge(1, 0);
	hasEdge(0, 2);
	hasEdge(3, 1);
	hasEdge(1, 2);
	hasEdge(2, 3);
}*/

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