제출 #791769

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

game

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

int n;
bool has_edge[1505][1505];

namespace ufds {
	int lnk[1505], sz[1505];
	
	void init(int n) {
		iota(lnk, lnk + n, 0);
		fill(sz, sz + n, 1);
	}
	int find(int x) {
		if (x == lnk[x]) return x;
		return lnk[x] = find(lnk[x]);
	}
	void unite(int a, int b) {
		a = find(a);
		b = find(b);
		if (a == b) return;
		if (sz[b] > sz[a]) swap(a, b);
		sz[a] += sz[b];
		lnk[b] = a;
	}
};

void initialize(int n) {
	::n = n;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			has_edge[i][j] = 1;
		}
	}
}

int hasEdge(int u, int v) {
	if (u > v) swap(u, v);
	ufds::init(n);
	has_edge[u][v] = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			if (has_edge[i][j]) ufds::unite(i, j);
		}
	}
	int comps = 0;
	for (int i = 0; i < n; i++) {
		if (i == ufds::find(i)) comps++;
	}
	return has_edge[u][v] = comps != 1;
}

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