Submission #512818

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
512818	2022-01-16 18:14:49	MathMate	Game (IOI14_game)	C++17	42 / 100	1053 ms	3588 KiB

game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
// #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)
{
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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