제출 #1278699

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1278699		IBory	게임 (IOI14_game)	C++20	100 / 100	193 ms	15468 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

const int MAX = 1505;
int C[MAX][MAX], N;

struct UF {
	int R[MAX], Z[MAX];
	UF() {
		iota(R, R + MAX, 0);
		fill(Z, Z + MAX, 1);
	}
	int Find(int n) {
		if (n == R[n]) return n;
		return R[n] = Find(R[n]);
	}
	void Union(int a, int b) {
		a = Find(a), b = Find(b);
		if (a == b) return;
		R[a] = b;
		Z[b] += Z[a];
	}
} UF;

void initialize(int n) {
	N = n;
}

int hasEdge(int a, int b) {
	a++; b++;
	a = UF.Find(a), b = UF.Find(b);
	if (a > b) swap(a, b);
	if (a == b) return 0;

	if (++C[a][b] == UF.Z[a] * UF.Z[b]) {
		UF.Union(a, b);
		int c = UF.Find(a);
		C[a][b] = 0;

		if (a == c) {
			for (int i = 1; i <= N; ++i) {
				int& t = (i <= b ? C[i][b] : C[b][i]);
				(i <= c ? C[i][c] : C[c][i]) += t;
				t = 0;
			}
		}
		else {
			for (int i = 1; i <= N; ++i) {
				int& t = (i <= a ? C[i][a] : C[a][i]);
				(i <= c ? C[i][c] : C[c][i]) += t;
				t = 0;
			}
		}

		return 1;
	}

	return 0;
}

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