Submission #512776

#	Time	Username	Problem	Language	Result	Execution time	Memory
512776		MathMate	Game (IOI14_game)	C++17	0 / 100	1 ms	344 KiB

game

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

const int MAX_N = 1.5e3 + 5;

vector <int> graf[MAX_N];

bool visited[MAX_N];

// 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

// Czyli tworzymy graf z grafu_ustawionych_i_mozliwych bez krawedzi {a, b}, nastepnie robimy DFS i sprawdzamy czy jest sciezka z a do b
// DFS -> O(MAX_N ^ 2)
// Wszystkich mozliwych krawedzi (ilosci zapytan) jest O(MAX_N ^ 2)
// Calkowita zlozonosc: O(MAX_N ^ 2 * MAX_N ^ 2) == O(MAX_N ^ 4)

int graf_ustawionych_i_mozliwych[MAX_N][MAX_N];

int n;

void initialize(int ilosc_wierzcholkow)
{
	n = ilosc_wierzcholkow;

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

void wyczysc()
{
	for(int i = 0; i < n; i++)
	{
		visited[i] = false;

		graf[i].clear();
	}
}

bool czy_dobra_krawedz(int kandydat_na_a, int kandydat_na_b, int a, int b)
{
	if((kandydat_na_a == a && kandydat_na_b == b) || (kandydat_na_a == b && kandydat_na_b == a))
	{
		return false;
	}

	else
	{
		return true;
	}
}

void stworz_graf(int a, int b)
{
	for(int i = 0; i < n; i++)
	{
		for(int j = 0; j < n; j++)
		{
			if(graf_ustawionych_i_mozliwych[i][j] && czy_dobra_krawedz(i, j, a, b))
			{
				graf[i].push_back(j);
				graf[j].push_back(i);
			}
		}
	}
}

void DFS(int v)
{
	visited[v] = true;

	for(auto& sasiad : graf[v])
	{
		if(!visited[sasiad])
		{
			DFS(sasiad);
		}
	}
}

int hasEdge(int a, int b)
{
	a--;
	b--;

	stworz_graf(a, b);

	DFS(a);

	// {a, b} nalezy do cyklu w grafie_ustawionych_i_mozliwych, {a, b} nie jest mostem w grafie_ustawionych_i_mozliwych
	if(visited[b])
	{
		return 0;
	}

	else
	{
		return 1;
	}

	wyczysc();
}

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