To jest zadanie interaktywne.

Tło zadania

Po pół roku sklep pana I ostatecznie przestał się utrzymywać. Pan I postanowił go odstąpić i zostać odkrywcą, aby badać rozległy, nieznany świat.

Kierując się starą księgą, znalazł w głębi wielkiej pustyni podziemny pałac stworzony przez nieznaną cywilizację. Pałac składa się z $N$ wielkich jaskiń i $M$ dwukierunkowych przejść łączących te jaskinie. Dzięki księdze pan I potrafi rozpoznać jaskinię, w której się znajduje, ale nie opisano w niej układu $M$ przejść. Utrudnia mu to szukanie nieprzebranych skarbów, które według legendy są ukryte w pałacu.

Teraz jednak pan I odkrył tajemniczy mechanizm, pozwalający uzyskiwać informacje o pałacu. Postanowił go wykorzystać do poznania układu połączeń. Pomóż mu w tym.

Treść zadania

Podziemny pałac można przedstawić jako nieskierowany graf prosty o $N$ wierzchołkach i $M$ krawędziach (w grafie prostym dowolne dwa wierzchołki są połączone bezpośrednio najwyżej jedną krawędzią). Jaskinie są ponumerowane od $0$ do $n-1$. Obecnie nie znasz krawędzi tego grafu.

Każda jaskinia ma źródło światła, które może być włączone lub wyłączone. Jaskinia jest oświetlona tylko wtedy, gdy jej źródło światła jest włączone. Początkowo wszystkie źródła światła są wyłączone, a ich stan można zmieniać wyłącznie za pomocą mechanizmu odkrytego przez pana I. Mechanizm umożliwia wykonanie czterech operacji:

1. Podajesz mechanizmowi numer $x$. Mechanizm zmienia stan źródła światła w jaskini $x$ oraz we wszystkich jaskiniach połączonych z nią bezpośrednim przejściem. Włączone źródła zostają wyłączone, a wyłączone zostają włączone.
2. Podajesz mechanizmowi numer $x$. Mechanizm pokazuje bieżący stan źródła światła w jaskini $x$.
3. Podajesz mechanizmowi dwa numery $x,y$, deklarując, że wiesz o istnieniu przejścia łączącego jaskinie $x$ i $y$, i polecasz mu je zapisać.
4. Podajesz mechanizmowi numer $x$. Mechanizm sprawdza, czy zapisano już wszystkie przejścia połączone z jaskinią $x$.

Mechanizm może rozpocząć następną operację dopiero po zakończeniu poprzedniej. Nie można korzystać z niego dowolnie: liczby wywołań poszczególnych operacji są ograniczone odpowiednio przez $L_m,L_q,M,L_c$. Napisz program pomagający panu I rozsądnie korzystać z mechanizmu, aby poprawnie odnaleźć wszystkie $M$ przejść.

Szczegóły implementacji

Nie musisz i nie powinieneś implementować funkcji głównej. Zaimplementuj jedynie funkcję explore(N, M), gdzie N i M oznaczają odpowiednio liczbę jaskiń i przejść. Z biblioteką interaktywną możesz komunikować się za pomocą następujących czterech funkcji:

1. modify(x)

• Ta funkcja wykonuje operację 1 dla numeru $x$.
• Musisz zapewnić $0\le x<N$. Funkcja nie zwraca wartości.

2. query(x)

• Ta funkcja wykonuje operację 2 dla numeru $x$.
• Musisz zapewnić $0\le x<N$. Funkcja zwraca 0 lub 1, oznaczając odpowiednio, że źródło światła w jaskini $x$ jest obecnie wyłączone (0) lub włączone (1).

3. report(x, y)

• Ta funkcja wykonuje operację 3 dla numerów $x,y$.
• Musisz zapewnić $0\le x,y<N$ oraz $x\ne y$. Funkcja nie zwraca wartości.

4. check(x)

• Ta funkcja wykonuje operację 4 dla numeru $x$.
• Musisz zapewnić $0\le x<N$. Funkcja zwraca 0 lub 1; zwraca 1 wtedy i tylko wtedy, gdy wszystkie przejścia połączone z jaskinią $x$ zostały już zapisane za pomocą operacji 3.

Podczas oceniania biblioteka interaktywna wywoła explore dokładnie raz.

Gwarantuje się, że używany graf jest całkowicie ustalony przed rozpoczęciem interakcji i nie jest konstruowany dynamicznie na podstawie interakcji z Twoim programem. Operacje interaktywne w tym zadaniu są zatem deterministyczne i nie musisz interesować się szczegółami ich implementacji w bibliotece.

Gwarantuje się, że przy przestrzeganiu limitów wywołań czas działania biblioteki interaktywnej nie przekracza 1 s. Ilość pamięci używanej przez bibliotekę jest stała i nie przekracza 128 MB.

Sposób implementacji

W katalogu roboczym zawodnika udostępniono plik template_explore.cpp/c/pas. Skopiuj go, zmień nazwę na explore.cpp/c/pas i napisz rozwiązanie na jego podstawie.

1. Dla zawodników używających C++ / C

• Upewnij się, że na początku programu znajduje się #include "explore.h".
• Interfejs funkcji explore, którą należy zaimplementować, jest następujący:

void explore(int N, int M);

• Dostępne funkcje interaktywne mają następujące interfejsy:

void modify(int x);
int query(int x);
void report(int x, int y);
int check(int x);

2. Dla zawodników używających Pascala

• Uwaga: składnia implementowania interfejsu w Pascalu jest dość złożona. Napisz rozwiązanie bezpośrednio na podstawie dostarczonego pliku template_explore.pas, zamiast implementować kod od zera.
• Interfejs funkcji explore, którą należy zaimplementować, jest następujący:

procedure _explore(N, M : longint);

• Uwaga: nazwa tej funkcji to _explore, a nie explore. Użycie explore spowoduje błąd kompilacji.
• Dostępne funkcje interaktywne mają następujące interfejsy:

procedure modify(x : longint);
function query(x : longint) : longint;
procedure report(x : longint; y : longint);
function check(x : longint) : longint;

Testowanie programu

Pliki grader.cpp/c i graderhelperlib.pas w katalogu zadania stanowią dostarczoną przez nas referencyjną implementację biblioteki interaktywnej. Implementacja używana podczas końcowych testów różni się od niej, dlatego rozwiązanie nie powinno zależeć od implementacji biblioteki.

1. Dla zawodników używających C/C++

• Aby skompilować plik wykonywalny, użyj w katalogu tego zadania poniższego polecenia.
• Dla C: gcc grader.c explore.c -o explore -O2 -lm
• Dla C++: g++ grader.cpp explore.cpp -o explore -O2 -lm

2. Dla zawodników używających Pascala

• Aby skompilować plik wykonywalny, użyj w katalogu tego zadania poniższego polecenia:

fpc grader.pas -o"explore" -O2

3. Dla otrzymanego pliku wykonywalnego

• Plik wykonywalny odczytuje ze standardowego wejścia dane w następującym formacie:

Pierwszy wiersz zawiera trzy liczby całkowite $L_m,L_q,L_c$, a drugi wiersz dwie liczby całkowite $N,M$, o znaczeniu opisanym w treści zadania.

Każdy z kolejnych $M$ wierszy zawiera dwie liczby całkowite $x,y$, opisujące przejście łączące jaskinie $x$ i $y$.

• Po wczytaniu danych biblioteka interaktywna wywoła funkcję explore dokładnie raz, testując Twoją funkcję na wczytanych danych. Gdy funkcja poprawnie zakończy działanie, biblioteka sprawdzi poprawność obliczeń. Jeśli są poprawne, wypisze Correct oraz informacje o liczbach wywołań funkcji interaktywnych; w przeciwnym razie wypisze odpowiedni komunikat o błędzie.

Interakcja

Załóżmy, że plik wykonywalny wczytał następujące dane:

100 200 300
3 2
0 1
1 2

Trzy liczby całkowite w pierwszym wierszu określają limity liczby wywołań trzech operacji: modify(x) można wywołać najwyżej 100 razy, query(x) najwyżej 200 razy, a check(x) najwyżej 300 razy.

Dwie liczby całkowite w drugim wierszu określają liczbę jaskiń i przejść: $N=3$, $M=2$.

Liczba wywołań report(x, y) nie może przekroczyć $M$, czyli w tym przykładzie 2.

Poniżej przedstawiono poprawny przebieg interakcji:

Opis dostarczonych plików

W katalogu tego zadania:

1. grader.cpp/c i graderhelperlib.pas to dostarczona przez nas referencyjna implementacja biblioteki interaktywnej.
2. explore.h i grader.pas to pliki nagłówkowe; nie musisz interesować się ich zawartością.
3. template_explore.cpp/c/pas to dostarczone przez nas przykładowe pliki źródłowe rozwiązania.
4. explore1.in, explore2.in i explore3.in to przykładowe dane wejściowe do testowania.

Zawodnicy powinni wykonać kopie zapasowe wszystkich dostarczonych plików. Ocenianiu podlega jedynie explore.c/cpp/pas z katalogu tego zadania. Zmiany w pozostałych plikach nie mają wpływu na ocenianie.

Podzadania

Podczas końcowego oceniania pobierany jest jedynie plik explore.cpp/c/pas. Modyfikowanie innych plików w katalogu zawodnika nie wpływa na ocenianie.

Obowiązują przede wszystkim takie same ograniczenia jak w zadaniach tradycyjnych. Na przykład błąd kompilacji skutkuje otrzymaniem 0 punktów za całe zadanie, a błąd wykonania, przekroczenie limitu czasu lub pamięci itp. skutkują otrzymaniem 0 punktów za odpowiedni test. Możesz odwoływać się jedynie do zdefiniowanych przez siebie zmiennych oraz zmiennych udostępnionych przez bibliotekę interaktywną i odpowiadających im obszarów pamięci. Próba dostępu do innych obszarów może spowodować błąd kompilacji lub wykonania.

Poza powyższymi warunkami otrzymasz pełną liczbę punktów za test wtedy i tylko wtedy, gdy:

1. Każde wywołanie funkcji jest poprawne, a liczby wywołań modify, query i check nie przekraczają odpowiednio $L_m,L_q,L_c$.
2. Ponieważ limit wywołań report wynosi $M$, każde wywołanie musi zapisywać nową, istniejącą krawędź. Przy każdym wywołaniu report(x, y) musi zatem istnieć przejście łączące jaskinie $x$ i $y$, a przed tym wywołaniem nie mogło wystąpić ani report(x, y), ani report(y, x).
3. Zaimplementowana przez Ciebie funkcja explore kończy działanie w zwykły sposób.
4. W chwili zakończenia funkcji explore wszystkie $M$ przejść zostały już zapisane za pomocą wywołań report.

Ograniczenia

Zadanie zawiera 25 testów, każdy wart 4 punkty. Rozmiary danych i związane z nimi ograniczenia dla każdego testu podano w poniższej tabeli.

Przypominamy, że graf używany podczas testowania jest całkowicie ustalony przed rozpoczęciem interakcji i nie jest konstruowany dynamicznie na podstawie interakcji z Twoim programem.

Oznaczenia w kolumnie szczególnych właściwości mają następujące znaczenie:

A: Gwarantuje się, że stopień każdego wierzchołka wynosi dokładnie $1$.

B: Gwarantuje się, że dla każdego $x>0$ istnieje dokładnie jedno $y<x$, dla którego jaskinie $x$ i $y$ są połączone bezpośrednim przejściem.

C: Istnieje permutacja $p_0,p_1,\ldots,p_{N-1}$ liczb od $0$ do $N-1$, taka że dla każdego $1\le i<N$ istnieje przejście łączące jaskinie $p_{i-1}$ i $p_i$.

D: Gwarantuje się, że graf jest spójny.

• Wskazówka: Twój program może odróżniać powyższe rodzaje danych na podstawie cyfry jedności otrzymanego parametru $N$.