제출 #596516

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
596516		Elias	게임 (IOI14_game)	C++17	0 / 100	1 ms	212 KiB

game

#include <bits/stdc++.h>

#ifndef _DEBUG
#include "game.h"
#endif

using namespace std;

vector<int> parent; // logn union find
vector<int> remain;

int find(int a)
{
	if (parent[a] == a)
		return a;
	return parent[a] = find(parent[a]);
}

void initialize(int n)
{
	parent = remain = vector<int>(n);
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
		remain[i] = n - 1;
	}
}

// if the remaining edge in group is queried, it exists, otherwise it doesn't. This guarantees there are at least 2 groups left until the end
int hasEdge(int u, int v)
{
	u = find(u);
	v = find(v);

	if (u == v)
		return 0;

	remain[u]--;
	remain[v]--;
	if (remain[u] == 0 || remain[v] == 0)
	{
		parent[u] = v;
		remain[v] += remain[u];
		return 1;
	}
	return 0;
}

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