Aoi i Bitaro są szpiegami należącymi do Narodowego Biura Informacyjnego państwa JOI. Tym razem ich misją jest przeprowadzenie tajnego śledztwa w państwie IOI. Bitaro przenika do IOI, a Aoi przekazuje mu instrukcje z JOI.

Przed infiltracją Aoi i Bitaro zdobyli mapę IOI. W państwie jest $N$ miast, ponumerowanych od $0$ do $N-1$, oraz $M$ dróg, ponumerowanych od $0$ do $M-1$. Droga $i$ ($0\le i\le M-1$) łączy dwukierunkowo miasta $A_i$ i $B_i$ i ma długość $C_i$. Między każdą parą miast można przejechać, korzystając z pewnych dróg. Bitaro przemieszcza się między miastami IOI tymi drogami.

Ponadto istnieje $Q$ planów śledztwa. Plan $j$ ($0\le j\le Q-1$) polega na zbadaniu miasta $T_j$ w IOI.

Początkowo wszystkie powyższe informacje otrzymali zarówno Aoi, jak i Bitaro. Następnie Bitaro rozpoczął infiltrację IOI.

Bitaro skutecznie uniknął licznych pościgów, pokonał zabójców i w końcu zdołał przedostać się do miasta $0$ w IOI. Jednak z powodu niezwykłej trudności operacji utracił część informacji o tym państwie. Dokładniej, utracił informacje o długościach $K$ dróg: $X_0,X_1,\ldots,X_{K-1}$. Innymi słowy, Bitaro nie zna już wartości $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Choć on utracił te informacje, Aoi nadal je posiada.

Bitaro natychmiast poinformował Aoi, o których drogach utracił informacje o długości.

Aby wykonać misję, Bitaro chce znać najkrótszą ścieżkę z miasta $0$ do każdego miasta objętego jednym z $Q$ planów śledztwa.

Aoi wyśle mu pomocniczy napis, którego każdy znak to 0 lub 1. Ze względu na ryzyko przechwycenia Aoi chce zminimalizować ilość przesłanych informacji.

Napisz program realizujący strategię Aoi polegającą na wysłaniu napisu do Bitaro na podstawie informacji o IOI, planach śledztwa i drogach, o których Bitaro utracił informacje. Napisz również program realizujący strategię Bitaro polegającą na wyznaczeniu najkrótszych ścieżek na podstawie posiadanych informacji i napisu od Aoi.

Szczegóły implementacji

Należy zgłosić dwa pliki.

Pierwszy plik to Aoi.cpp. Ma realizować strategię Aoi i implementować następującą funkcję. Program powinien dołączyć Aoi.h za pomocą dyrektywy preprocesora #include.

• std::string aoi(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X)

  Funkcja jest wywoływana tylko raz dla każdego przypadku testowego.

  • Parametr N to liczba miast $N$ w królestwie IOI.
  • Parametr M to liczba dróg $M$ w królestwie IOI.
  • Parametr Q to liczba planów śledztwa $Q$.
  • Parametr K to liczba dróg, o których długości Bitaro utracił informacje, oznaczona przez $K$.
  • Parametry A, B, C są tablicami długości $M$. Oznaczają, że droga $i$ ($0\le i\le M-1$) łączy dwukierunkowo miasta A[i] i B[i] i ma długość C[i].
  • Parametr T jest tablicą długości $Q$. Plan $j$ ($0\le j\le Q-1$) polega na zbadaniu miasta T[j].
  • Parametr X jest tablicą długości $K$. Wskazuje, że Bitaro utracił informacje o długościach dróg X[0], X[1], ..., X[K-1].
  • Wartość zwracana to napis $s$, który Aoi wysyła do Bitaro.
  • Każdy znak napisu $s$ musi być 0 lub 1. W przeciwnym razie program otrzyma werdykt Wrong Answer [1].
  • Długość napisu $s$ nie może przekraczać $12\,000$. W przeciwnym razie program otrzyma werdykt Wrong Answer [2].

Drugi plik to Bitaro.cpp. Ma realizować strategię Bitaro i implementować następującą funkcję. Program powinien dołączyć Bitaro.h za pomocą dyrektywy preprocesora #include.

• void bitaro(int N, int M, int Q, int K, std::vector<int> A, std::vector<int> B, std::vector<long long> C, std::vector<int> T, std::vector<int> X, std::string s)

  Funkcja jest wywoływana tylko raz, po wywołaniu funkcji aoi.

  • Parametr N to liczba miast $N$ w królestwie IOI.
  • Parametr M to liczba dróg $M$ w królestwie IOI.
  • Parametr Q to liczba planów śledztwa $Q$.
  • Parametr K to liczba dróg, o których długości Bitaro utracił informacje, oznaczona przez $K$.
  • Parametry A, B, C są tablicami długości $M$. Oznaczają, że droga $i$ ($0\le i\le M-1$) łączy dwukierunkowo miasta A[i] i B[i] i ma długość C[i].
  • Parametr T jest tablicą długości $Q$. Plan $j$ ($0\le j\le Q-1$) polega na zbadaniu miasta T[j].
  • Parametr X jest tablicą długości $K$. Wskazuje, że Bitaro utracił informacje o długościach dróg X[0], X[1], ..., X[K-1].
  • Argument s jest napisem, którego każdy znak to 0 lub 1, przesłanym przez Aoi do Bitaro.

W pliku Bitaro.cpp program może wywoływać następującą funkcję.

• void answer(const std::vector<int> &e)

  W wywołaniu numer $j+1$ ($0\le j\le Q-1$) należy podać najkrótszą ścieżkę z miasta $0$ do miasta $T_j$, będącego celem planu śledztwa $j$.

  • Parametr e jest tablicą reprezentującą najkrótszą ścieżkę z miasta $0$ do miasta $T_j$.
  • Niech $n$ będzie długością tablicy e. Elementy e[0], e[1], ..., e[n-1] to numery dróg najkrótszej ścieżki z miasta $0$ do miasta $T_j$, w kolejności przechodzenia.
  • Jeśli istnieje wiele najkrótszych ścieżek, można podać dowolną z nich.
  • Każdy element parametru e musi być między $0$ a $M-1$. W przeciwnym razie program otrzyma werdykt Wrong Answer [3].

  • Ciąg dróg wskazany przez argument e musi tworzyć ścieżkę z miasta $0$ do miasta $T_j$. Formalnie muszą być spełnione następujące warunki.

    Istnieje ciąg liczb $u_0,u_1,\ldots,u_n$, dla którego:

    • $u_0=0$.
    • $u_n=T_j$.
    • Droga e[k] (gdzie $0\le k\le n-1$) łączy miasta $u_k$ i $u_{k+1}$.

    Jeśli te warunki nie są spełnione, program otrzyma werdykt Wrong Answer [4].

  • Jeśli ciąg dróg wskazany przez e nie jest najkrótszą ścieżką z miasta $0$ do miasta $T_j$ spośród wszystkich ścieżek rozpoczynających się w $0$ i kończących w $T_j$, program otrzyma werdykt Wrong Answer [5]. Długość ścieżki jest sumą długości użytych dróg.

  • Funkcję answer należy wywołać dokładnie $Q$ razy. Jeśli po zakończeniu funkcji bitaro liczba wywołań answer nie jest równa $Q$, program otrzyma werdykt Wrong Answer [6].

Ważne uwagi

• Program może implementować inne funkcje do użytku wewnętrznego lub korzystać ze zmiennych globalnych. Zgłoszone pliki zostaną skompilowane wraz z programem oceniającym do jednego pliku wykonywalnego. Wszystkie zmienne globalne i funkcje wewnętrzne należy zadeklarować w nienazwanej przestrzeni nazw, aby uniknąć konfliktów z innymi plikami. Podczas oceny program zostanie uruchomiony jako dwa procesy: Aoi i Bitaro. Nie mogą one współdzielić zmiennych globalnych.
• Program nie może używać standardowego wejścia ani standardowego wyjścia. Nie może też w żaden sposób komunikować się z innymi plikami. Może jednak wypisywać informacje diagnostyczne na standardowe wyjście błędów.

Kompilacja i uruchomienie testowe

Ze strony konkursu można pobrać archiwum z przykładowym programem oceniającym do testowania programu. Archiwum zawiera również przykładowy plik źródłowy rozwiązania.

Przykładowy program oceniający to plik grader.cpp. Aby przetestować program, umieść pliki grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h w tym samym katalogu i uruchom poniższe polecenie kompilacji. Można zamiast tego uruchomić zawarty w archiwum skrypt compile.sh.

g++ -std=gnu++20 -O2 -o grader grader.cpp Aoi.cpp Bitaro.cpp

Po pomyślnej kompilacji powstanie plik wykonywalny grader.

Rzeczywisty program oceniający różni się od przykładowego. Przykładowy program jest uruchamiany jako jeden proces, który czyta dane ze standardowego wejścia i wypisuje wyniki na standardowe wyjście oraz standardowe wyjście błędów.

Wejście przykładowego programu oceniającego

Przykładowy program oceniający czyta następujące dane ze standardowego wejścia.

$$ \begin{array}{l} N\ M\\ A_0\ B_0\ C_0\\ A_1\ B_1\ C_1\\ \vdots\\ A_{M-1}\ B_{M-1}\ C_{M-1}\\ Q\\ T_0\ T_1\ \ldots\ T_{Q-1}\\ K\\ X_0\ X_1\ \ldots\ X_{K-1} \end{array} $$

Wyjście przykładowego programu oceniającego

Przykładowy program oceniający wypisuje następujące informacje na standardowe wyjście i standardowe wyjście błędów (cudzysłowy w opisie służą czytelności).

• Jeśli program otrzyma werdykt Wrong Answer [1], [2], [3], [4] lub [6], przykładowy program wypisze jego typ, na przykład Wrong Answer [1], na standardowe wyjście błędów. Na standardowe wyjście nie zostanie wypisane nic.
• W przeciwnym razie długość napisu $s$ zwróconego przez aoi zostanie wypisana na standardowe wyjście błędów w formacie Accepted: 2024. Ponadto długość ścieżki podanej w wywołaniu numer $j+1$ ($0\le j\le Q-1$) funkcji answer zostanie wypisana w wierszu numer $j+1$ standardowego wyjścia. Przykładowy program oceniający nie sprawdza, czy ścieżka jest najkrótsza.

Jeśli program spełnia warunki kilku typów Wrong Answer, przykładowy program oceniający zgłasza tylko jeden z nich.

Ograniczenia

Wszystkie dane wejściowe spełniają następujące warunki:

• $2\le N\le 10\,000$.
• $1\le M\le 20\,000$.
• $1\le Q\le 16$.
• $1\le K\le 300$.
• $0\le A_i<B_i\le N-1$ ($0\le i\le M-1$).
• $(A_i,B_i)\ne(A_j,B_j)$ ($0\le i<j\le M-1$).
• $1\le C_i\le 10^{12}$ ($0\le i\le M-1$).
• $1\le T_j\le N-1$ ($0\le j\le Q-1$).
• $T_j\ne T_k$ ($0\le j<k\le Q-1$).
• $0\le X_k\le M-1$ ($0\le k\le K-1$).
• $X_k\ne X_l$ ($0\le k<l\le K-1$).
• Z każdego miasta można dotrzeć do każdego innego, przechodząc pewnymi drogami.
• Wszystkie wartości wejściowe są liczbami całkowitymi.

Ocena

Jeśli w którymkolwiek przypadku testowym program otrzyma dowolny werdykt Wrong Answer [1]–[6] (zobacz Szczegóły implementacji) lub wystąpi dowolny błąd wykonania (TLE — przekroczenie limitu czasu, MLE — przekroczenie limitu pamięci, nieprawidłowe zakończenie itp.), wynik wyniesie $0$ punktów.

W przeciwnym razie ocena zależy od największej długości napisu $s$ zwróconego przez funkcję aoi we wszystkich przypadkach testowych tego zadania, oznaczonej przez $L$.

• Jeśli $1561\le L\le 12\,000$, wynik wyniesie $\left\lfloor\frac{100\,000}{L-560}\right\rfloor$ punktów.
• Jeśli $0\le L\le 1560$, wynik wyniesie $100$ punktów.

Tutaj $\lfloor x\rfloor$ oznacza największą liczbę całkowitą nie większą niż $x$.

Przykładowa komunikacja

Poniżej podano przykładowe wejście dla przykładowego programu oceniającego i odpowiadające mu wywołania funkcji.

Wejście 1

3 3
1 2 1
0 2 2
0 1 3
2
2 1
2
0 1

Przykładowe wywołania funkcji

Najkrótszą ścieżkę z miasta $0$ do miasta $1$ można uzyskać, przechodząc kolejno drogami $1$ i $0$ albo tylko drogą $2$. Dlatego w drugim wywołaniu funkcji answer w tym przykładzie dopuszczalne jest również answer([2]).

Plik sample-01-in.txt, który można pobrać ze strony konkursu, odpowiada przykładowemu wejściu 1.

Pliki sample-01-in.txt i sample-02-in.txt dostępne do pobrania ze strony konkursu mogą służyć jako wejście przykładowego programu oceniającego.