Submission #512818

#	Time	Username	Problem	Language	Result	Execution time	Memory
512818		MathMate	Game (IOI14_game)	C++17	42 / 100	1053 ms	3588 KiB

game

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

const int MAX_N = 1.5e3 + 5;

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 = i + 1; j < n; j++)
		{
			graf_ustawionych_i_mozliwych[i][j] = (i != j);
			graf_ustawionych_i_mozliwych[j][i] = (i != j);
		}
	}
}

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

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

	for(int i = 0; i < n; i++)
	{
		if(!visited[i] && graf_ustawionych_i_mozliwych[v][i])
		{
			DFS(i);
		}
	}
}

int hasEdge(int a, int b)
{
	// usuwamy krawedz {a, b}

	graf_ustawionych_i_mozliwych[a][b] = 0;
	graf_ustawionych_i_mozliwych[b][a] = 0;

	DFS(a);

	// true -> {a, b} nie jest mostem w grafie_ustawionych_i_mozliwych
	// false -> {a, b} nalezy do cyklu w grafie_ustawionych_i_mozliwych
	bool ok = !visited[b];

	if(ok)
	{
		graf_ustawionych_i_mozliwych[a][b] = 1;
		graf_ustawionych_i_mozliwych[b][a] = 1;
	}

	wyczysc();

	return ok;
}

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