Submission #512832

#	Time	Username	Problem	Language	Result	Execution time	Memory
512832		MathMate	Game (IOI14_game)	C++17	100 / 100	337 ms	19344 KiB

game

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

const int MAX_N = 1.5e3 + 5;

// graf_ustawionych -> graf krawedzi ustawionych i przyjmuje, ze mozliwe nie sa ustawione
// graf_ustawionych_i_mozliwych -> graf krawedzi ustawionych i przyjmuje, ze mozliwe tez sa ustawione
// Na poczatku ma wszystkie krawedzie sa nieustawione w grafie graf_ustawionych
// Na poczatku ma wszystkie krawedzie sa ustawione w grafie graf_ustawionych_i_mozliwych
// Na zapytanie o to czy {a, b} sa polaczone:
// * "YES" -> gdy {a, b} jest mostem w grafie_ustawionych_i_mozliwych
// * "NO" -> w przeciwnym przypadku
// Czyli innymi slowy odpowiadamy:
// * "YES" -> w przeciwnym przypadku
// * "NO" -> gdy {a, b} nalezy do cyklu w grafie_ustawionych_i_mozliwych

// Zeby rozwiazac to szybciej niz w O(MAX_N ^ 4) -> czyli w O(MAX_N ^ 2)
// Do znajdowania mostow posluzymy sie struktura F & U (DSU)
// I tablice ilosc_krawedzi_laczacych_wierzcholki[a][b], ktora bedzie mowila nam
// Ile krawedzi laczy find_set(a) z find_set(b)
// Krawedz {a, b} bedzie mostem w grafie_ustawionych_i_mozliwych,
// Jesli ilosc_krawedzi_laczacych_wierzcholki[a][b] == 1
// union_sets() zajmuje O(n), a find_set() zajmuje O(1)

// Poczatkowo ilosc_krawedzi_laczacych_wierzcholki[a][b] == 1 dla kazdej pary {a, b},
// Gdzie a != b

// Jesli odpowiadamy "NO", to zmniejszamy ilosc_krawedzi_laczacych_wierzcholki[a][b] i ilosc_krawedzi_laczacych_wierzcholki[b][a] o 1
// Jesli odpowiadamy "YES", to dla kazdego reprezentanta i,
// Robimy ilosc_krawedzi_laczacych_wierzcholki[a][i] += ilosc_krawedzi_laczacych_wierzcholki[b][i]

// Operacji union_set() moze byc maksymalnie (n - 1), wiec wszystkie operacje union_set() to O(MAX_N ^ 2)
// Update ilosc_krawedzi_laczacych_wierzcholki[a][b] w przypadku "YES", to O(n), ale operacji update wykonamy maksymalnie (n - 1), wiec wszystkie updaty to O(MAX_N ^ 2)

// Calkowita zlozonosc: O(MAX_N ^ 2)

int ilosc_krawedzi_laczacych_wierzcholki[MAX_N][MAX_N];

vector <int> rodzic(MAX_N);

int n;

int find_set(int v)
{
	if(v == rodzic[v])
	{
		return v;
	}

	return rodzic[v] = find_set(rodzic[v]);
}

void make_set(int v)
{
	rodzic[v] = v;
}

void union_sets(int a, int b)
{
	a = find_set(a);
	b = find_set(b);

	for(int i = 0; i < n; i++)
	{
		int reprezentant_i = find_set(i);

		if(reprezentant_i == i)
		{
			ilosc_krawedzi_laczacych_wierzcholki[a][i] += ilosc_krawedzi_laczacych_wierzcholki[b][i];

			ilosc_krawedzi_laczacych_wierzcholki[i][a] = ilosc_krawedzi_laczacych_wierzcholki[a][i];
		}
	}

	rodzic[b] = a;
}

bool check(int a, int b)
{
	return find_set(a) == find_set(b);
}

void initialize(int ilosc_wierzcholkow)
{
	n = ilosc_wierzcholkow;

	for(int i = 0; i < n; i++)
	{
		make_set(i);
	}

	for(int i = 0; i < n; i++)
	{
		for(int j = i + 1; j < n; j++)
		{
			ilosc_krawedzi_laczacych_wierzcholki[i][j] = (i != j);
			ilosc_krawedzi_laczacych_wierzcholki[j][i] = (i != j);
		}
	}
}

int hasEdge(int a, int b)
{
	a = find_set(a);
	b = find_set(b);

	if(a == b)
	{
		return 0;
	}

	bool ok = (ilosc_krawedzi_laczacych_wierzcholki[a][b] == 1);

	if(ok)
	{
		union_sets(a, b);
	}

	else
	{
		ilosc_krawedzi_laczacych_wierzcholki[a][b]--;
		ilosc_krawedzi_laczacych_wierzcholki[b][a]--;
	}

	return ok;
}

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