Aoi e Bitaro sono spie appartenenti all'Ufficio Nazionale di Informazione del paese di JOI. La loro missione questa volta è condurre un'indagine sotto copertura nel paese di IOI. Bitaro si infiltra nel paese di IOI, mentre Aoi impartisce istruzioni a Bitaro dal paese di JOI.

Prima dell'infiltrazione, Aoi e Bitaro hanno ottenuto una mappa del paese di IOI. Il paese di IOI ha $N$ città, numerate da $0$ a $N-1$. Inoltre, ci sono $M$ strade nel paese di IOI, numerate da $0$ a $M-1$. La strada $i$ ($0\le i\le M-1$) collega la città $A_i$ e la città $B_i$ in modo bidirezionale, con una lunghezza pari a $C_i$. È possibile viaggiare tra qualsiasi coppia di città percorrendo alcune strade. Bitaro si sposta tra le città del paese di IOI percorrendo queste strade.

Inoltre, ci sono $Q$ piani di indagine. Il $j$-esimo piano ($0\le j\le Q-1$) prevede di indagare sulla città $T_j$ nel paese di IOI.

Tutte le informazioni di cui sopra sono state inizialmente fornite sia ad Aoi che a Bitaro. Successivamente, Bitaro ha proceduto con l'infiltrazione nel paese di IOI.

Bitaro è riuscito a eludere numerosi inseguitori, ha sconfitto degli assassini e infine è riuscito a infiltrarsi nella città $0$ del paese di IOI. Tuttavia, a causa della natura estremamente difficile dell'operazione di infiltrazione, Bitaro ha perso alcune informazioni sul paese di IOI. Nello specifico, Bitaro ha perso le informazioni sulla lunghezza di $K$ strade, ovvero le strade $X_0,X_1,\ldots,X_{K-1}$. In altre parole, Bitaro non conosce più i valori di $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Si noti che mentre Bitaro ha perso queste informazioni, Aoi le conserva ancora.

Bitaro ha immediatamente riferito ad Aoi di quali strade avesse perso le informazioni sulla lunghezza.

Per compiere la missione, Bitaro vuole conoscere un cammino minimo dalla città $0$ a ciascuna delle città obiettivo dei $Q$ piani di indagine.

Aoi invierà a Bitaro una stringa in cui ogni carattere è 0 oppure 1 per assisterlo. A causa del rischio di intercettazione, Aoi vuole ridurre al minimo il contenuto inviato a Bitaro.

Scrivi un programma per implementare la strategia di Aoi per inviare una stringa a Bitaro, date le informazioni sul paese di IOI, i piani di indagine e le strade di cui Bitaro ha perso le informazioni. Inoltre, scrivi un programma per implementare la strategia di Bitaro per trovare i cammini minimi date le informazioni in suo possesso e la stringa inviata da Aoi.

Dettagli di implementazione

Devi inviare 2 file.

Il primo file è Aoi.cpp. Questo file è destinato a implementare la strategia di Aoi e deve implementare le seguenti funzioni. Il programma deve includere Aoi.h usando la direttiva del preprocessore #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)

Questa funzione viene chiamata una sola volta per ciascun caso di test.

• Il parametro N è il numero di città nel Regno di IOI $N$.
• Il parametro M è il numero di strade nel Regno di IOI $M$.
• Il parametro Q è il numero di piani di indagine $Q$.
• Il parametro K è il numero di strade di cui Bitaro ha perso le informazioni sulla lunghezza, indicato con $K$.
• I parametri A, B, C sono array di lunghezza $M$. Essi indicano che la strada $i$ ($0\le i\le M-1$) collega la città A[i] e la città B[i] in modo bidirezionale, con una lunghezza pari a C[i].
• Il parametro T è un array di lunghezza $Q$. Esso indica che il $j$-esimo piano ($0\le j\le Q-1$) prevede di indagare sulla città T[j].
• Il parametro X è un array di lunghezza $K$. Esso indica che Bitaro ha perso le informazioni sulla lunghezza delle strade X[0], X[1], ..., X[K-1].
• Il valore di ritorno è la stringa $s$ che Aoi invia a Bitaro.
• Ogni carattere della stringa $s$ deve essere 0 oppure 1. Se questa condizione non è soddisfatta, il tuo programma sarà giudicato come Wrong Answer [1].
• La lunghezza della stringa $s$ deve essere al massimo $12\,000$. Se questa condizione non è soddisfatta, il tuo programma sarà giudicato come Wrong Answer [2].

Il secondo file è Bitaro.cpp. Questo file è destinato a implementare la strategia di Bitaro e deve implementare le seguenti funzioni. Il programma deve includere Bitaro.h usando la direttiva del preprocessore #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)

Questa funzione viene chiamata una sola volta dopo che è stata chiamata la funzione aoi.

• Il parametro N è il numero di città nel Regno di IOI $N$.
• Il parametro M è il numero di strade nel Regno di IOI $M$.
• Il parametro Q è il numero di piani di indagine $Q$.
• Il parametro K è il numero di strade di cui Bitaro ha perso le informazioni sulla lunghezza, indicato con $K$.
• I parametri A, B, C sono array di lunghezza $M$. Essi indicano che la strada $i$ ($0\le i\le M-1$) collega la città A[i] e la città B[i] in modo bidirezionale, con una lunghezza pari a C[i].
• Il parametro T è un array di lunghezza $Q$. Esso indica che il $j$-esimo piano ($0\le j\le Q-1$) prevede di indagare sulla città T[j].
• Il parametro X è un array di lunghezza $K$. Esso indica che Bitaro ha perso le informazioni sulla lunghezza delle strade X[0], X[1], ..., X[K-1].
• L'argomento s è una stringa in cui ogni carattere è 0 oppure 1, che rappresenta la stringa inviata da Aoi a Bitaro.

All'interno di Bitaro.cpp, il tuo programma può chiamare la seguente funzione.

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

Nella $(j+1)$-esima chiamata ($0\le j\le Q-1$) a questa funzione, devi rispondere con il cammino minimo dalla città $0$ alla città $T_j$, che è l'obiettivo del $j$-esimo piano di indagine.

• Il parametro e è un array che rappresenta il cammino minimo dalla città $0$ alla città $T_j$.
• Sia $n$ la lunghezza dell'array e. Gli elementi e[0], e[1], ..., e[n-1] sono gli indici delle strade nel cammino minimo dalla città $0$ alla città $T_j$, nell'ordine di percorrenza.
• Se esistono più cammini minimi possibili, uno qualsiasi di essi può essere scelto come risposta.
• Ogni elemento del parametro e deve essere compreso tra $0$ e $M-1$. Se questa condizione non è soddisfatta, il tuo programma sarà giudicato come Wrong Answer [3].

• La sequenza di strade indicata dall'argomento e deve formare un cammino dalla città $0$ alla città $T_j$. Più formalmente, deve soddisfare le seguenti condizioni.

  Esiste una sequenza di numeri $u_0,u_1,\ldots,u_n$ tale che

  • $u_0=0$.
  • $u_n=T_j$.
  • La strada e[k] (dove $0\le k\le n-1$) collega la città $u_k$ e la città $u_{k+1}$.

  Se queste condizioni non sono soddisfatte, il tuo programma sarà giudicato come Wrong Answer [4].

• Se la sequenza di strade indicata dall'argomento e non è il cammino minimo dalla città $0$ alla città $T_j$ tra tutti i cammini che partono dalla città $0$ e terminano nella città $T_j$, il tuo programma sarà giudicato come Wrong Answer [5]. Qui, la lunghezza del cammino è definita come la somma delle lunghezze delle strade utilizzate.

• La funzione answer deve essere chiamata esattamente $Q$ volte. Se il numero di chiamate alla funzione answer non è uguale a $Q$ al termine dell'esecuzione della funzione bitaro, il tuo programma sarà giudicato come Wrong Answer [6].

Avvisi importanti

• Il tuo programma può implementare altre funzioni per uso interno o utilizzare variabili globali. I file inviati verranno compilati con il grader e diventeranno un unico file eseguibile. Tutte le variabili globali e le funzioni interne devono essere dichiarate in un namespace anonimo (unnamed namespace) per evitare conflitti con altri file. Durante la valutazione, verrà eseguito come due processi distinti per Aoi e Bitaro. Il processo di Aoi e il processo di Bitaro non possono condividere variabili globali.
• Il tuo programma non deve utilizzare lo standard input e lo standard output. Il tuo programma non deve comunicare con altri file con alcun metodo. Tuttavia, il tuo programma può stampare informazioni di debug sullo standard error.

Compilazione ed esecuzione di prova

Puoi scaricare dalla pagina web della gara un file di archivio che contiene il grader di esempio per testare il tuo programma. Il file di archivio contiene anche un file sorgente di esempio del tuo programma.

Il grader di esempio è il file grader.cpp. Per testare il tuo programma, metti grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h nella stessa directory ed esegui il seguente comando per compilare i tuoi programmi. In alternativa, puoi eseguire compile.sh contenuto nel file di archivio.

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

Quando la compilazione ha successo, viene generato il file eseguibile grader.

Nota che il grader effettivo è diverso dal grader di esempio. Il grader di esempio verrà eseguito come un singolo processo, che leggerà i dati di input dallo standard input e scriverà i risultati sullo standard output e sullo standard error.

Input per il grader di esempio

Il grader di esempio legge i seguenti dati dallo standard input.

$$ \begin{gathered} 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{gathered} $$

Output del grader di esempio

Il grader di esempio stampa le seguenti informazioni sullo standard output e sullo standard error (virgolette per chiarezza).

• Se il tuo programma viene giudicato come Wrong Answer [1], [2], [3], [4] oppure [6], il grader di esempio scrive il suo tipo come Wrong Answer [1] sullo standard error. Non verrà stampato nulla sullo standard output.
• In caso contrario, la lunghezza della stringa $s$ restituita dalla funzione aoi verrà stampata sullo standard error nel formato Accepted: 2024. Inoltre, la lunghezza del cammino nella $(j+1)$-esima chiamata ($0\le j\le Q-1$) alla funzione answer verrà stampata sulla $(j+1)$-esima riga dello standard output. Il programma di valutazione di esempio non controlla se il cammino sia effettivamente il più breve.

Se il tuo programma soddisfa le condizioni di diversi tipi di Wrong Answer, il grader di esempio ne segnala solo uno.

Vincoli

Tutti i dati di input soddisfano le seguenti condizioni:

• $2\le N\le10\,000$.
• $1\le M\le20\,000$.
• $1\le Q\le16$.
• $1\le K\le300$.
• $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\le10^{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$).
• È possibile viaggiare da qualsiasi città a qualsiasi altra città percorrendo alcune strade.
• Tutti i valori di input sono interi.

Valutazione

Se il tuo programma viene giudicato con un qualsiasi tipo di Wrong Answer [1]–[6] (vedi Dettagli di implementazione) o con un qualsiasi tipo di errore di runtime (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), terminazione anomala, ecc.) in uno qualsiasi dei casi di test, il tuo punteggio è $0$ punti.

Altrimenti, la valutazione si basa sulla lunghezza massima della stringa restituita $s$ dalla funzione aoi, indicata con $L$, su tutti i casi di test per questo problema.

• Se $1561\le L\le12\,000$, il punteggio è $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ punti.
• Se $0\le L\le1560$, il punteggio è $100$ punti.

Qui, $\lfloor x\rfloor$ rappresenta il più grande intero non maggiore di $x$.

Esempi

Ecco un input di esempio per il grader di esempio e le corrispondenti chiamate di funzione.

Input 1

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

Chiamate di funzione di esempio

Il cammino minimo dalla città $0$ alla città $1$ si ottiene percorrendo le strade $1$ e $0$ in questo ordine, oppure passando semplicemente per la strada $2$. Pertanto, per la seconda chiamata alla funzione answer in questo esempio, è accettabile anche chiamare answer([2]).

Il file che può essere scaricato dal sito della gara, sample-01-in.txt, corrisponde all'esempio di input 1.

I file sample-01-in.txt e sample-02-in.txt inclusi nei file scaricabili dal sito della gara possono essere utilizzati come input per il grader di esempio.