제출 #256794

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
256794		SpeedOfMagic	Game (IOI14_game)	C++17	15 / 100	2 ms	384 KiB

game

#include "game.h"

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> cnt;  // cnt[i][j] = how many edges are forbidden between i and j
vector<int> repr, siz;

int ffind(int a) { return (a == repr[a]) ? a : repr[a] = ffind(repr[a]); }

void unite(int u, int v) {  // O(N), O(N^2) amortized
	u = ffind(u); v = ffind(v);
	if (u == v) return;
	if (siz[u] > siz[v]) swap(u, v);
	repr[u] = v; siz[v] += siz[u];
	for (size_t i = 0; i < cnt.size(); ++i)
		cnt[v][i] += cnt[u][i];
}

void initialize(int n) {
	cnt.resize(n, vector<int>(n, 0));
	repr.resize(n);
	for (int i = 0; i < n; ++i)
		repr[i] = i;
	siz.resize(n, 1);
}

int hasEdge(int u, int v) {
	int ru = ffind(u), rv = ffind(v);
	if (cnt[ru][rv] + 1 == siz[ru] * siz[rv]) {  // We must unite!
		unite(ru, rv);
		return 1;
	} else {  // Nah, we can wait
		++cnt[ru][rv];
		++cnt[rv][ru];
		return 0;
	}
}

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