Aoi e Bitaro são espiões do Departamento Nacional de Informações do país JOI. Sua missão desta vez é realizar uma investigação secreta no país IOI. Bitaro se infiltra no país IOI, enquanto Aoi lhe dá instruções a partir do país JOI.

Antes da infiltração, Aoi e Bitaro obtiveram um mapa do país IOI. O país IOI tem $N$ cidades, numeradas de $0$ a $N-1$. Além disso, há $M$ estradas, numeradas de $0$ a $M-1$. A estrada $i$ ($0\le i\le M-1$) conecta as cidades $A_i$ e $B_i$ nos dois sentidos e tem comprimento $C_i$. É possível viajar entre qualquer par de cidades percorrendo algumas estradas. Bitaro se desloca entre as cidades do país IOI por essas estradas.

Além disso, há $Q$ planos de investigação. O plano $j$ ($0\le j\le Q-1$) consiste em investigar a cidade $T_j$ do país IOI.

Todas as informações acima foram inicialmente fornecidas tanto a Aoi quanto a Bitaro. Em seguida, Bitaro iniciou a infiltração no país IOI.

Bitaro conseguiu escapar de numerosos perseguidores, derrotou assassinos e finalmente se infiltrou na cidade $0$ do país IOI. Porém, devido à extrema dificuldade da operação, Bitaro perdeu parte das informações sobre o país IOI. Especificamente, perdeu os comprimentos de $K$ estradas: $X_0,X_1,\ldots,X_{K-1}$. Em outras palavras, já não conhece os valores $C_{X_0},C_{X_1},\ldots,C_{X_{K-1}}$. Embora Bitaro tenha perdido essas informações, Aoi ainda as possui.

Bitaro informou imediatamente a Aoi de quais estradas havia perdido as informações de comprimento.

Para cumprir a missão, Bitaro quer conhecer um caminho mínimo da cidade $0$ até cada uma das cidades visadas pelos $Q$ planos de investigação.

Aoi enviará a Bitaro uma string em que cada caractere é 0 ou 1 para ajudá-lo. Devido ao risco de interceptação, Aoi quer minimizar o conteúdo enviado a Bitaro.

Escreva um programa que implemente a estratégia de Aoi para enviar uma string a Bitaro, dadas as informações sobre o país IOI, os planos de investigação e as estradas cujas informações Bitaro perdeu. Escreva também um programa que implemente a estratégia de Bitaro para encontrar os caminhos mínimos, dadas as informações que possui e a string enviada por Aoi.

Detalhes de implementação

Você deve enviar 2 arquivos.

O primeiro é Aoi.cpp. Esse arquivo deve implementar a estratégia de Aoi por meio das funções a seguir. O programa deve incluir Aoi.h usando a diretiva de pré-processamento #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)

  Esta função é chamada apenas uma vez por caso de teste.

  • O parâmetro N é o número $N$ de cidades do Reino IOI.
  • O parâmetro M é o número $M$ de estradas do Reino IOI.
  • O parâmetro Q é o número $Q$ de planos de investigação.
  • O parâmetro K é o número $K$ de estradas cujas informações de comprimento Bitaro perdeu.
  • Os parâmetros A, B, C são vetores de comprimento $M$. Indicam que a estrada $i$ ($0\le i\le M-1$) conecta as cidades A[i] e B[i] nos dois sentidos, com comprimento C[i].
  • O parâmetro T é um vetor de comprimento $Q$. Indica que o plano $j$ ($0\le j\le Q-1$) consiste em investigar a cidade T[j].
  • O parâmetro X é um vetor de comprimento $K$. Indica que Bitaro perdeu as informações de comprimento das estradas X[0], X[1], ..., X[K-1].
  • O valor de retorno é a string $s$ que Aoi envia a Bitaro.
  • Cada caractere da string $s$ deve ser 0 ou 1. Se essa condição não for satisfeita, seu programa receberá o veredito Wrong Answer [1].
  • O comprimento da string $s$ deve ser no máximo $12\,000$. Se essa condição não for satisfeita, seu programa receberá o veredito Wrong Answer [2].

O segundo arquivo é Bitaro.cpp. Esse arquivo deve implementar a estratégia de Bitaro por meio das funções a seguir. O programa deve incluir Bitaro.h usando a diretiva de pré-processamento #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)

  Esta função é chamada apenas uma vez, após a chamada à função aoi.

  • O parâmetro N é o número $N$ de cidades do Reino IOI.
  • O parâmetro M é o número $M$ de estradas do Reino IOI.
  • O parâmetro Q é o número $Q$ de planos de investigação.
  • O parâmetro K é o número $K$ de estradas cujas informações de comprimento Bitaro perdeu.
  • Os parâmetros A, B, C são vetores de comprimento $M$. Indicam que a estrada $i$ ($0\le i\le M-1$) conecta as cidades A[i] e B[i] nos dois sentidos, com comprimento C[i].
  • O parâmetro T é um vetor de comprimento $Q$. Indica que o plano $j$ ($0\le j\le Q-1$) consiste em investigar a cidade T[j].
  • O parâmetro X é um vetor de comprimento $K$. Indica que Bitaro perdeu as informações de comprimento das estradas X[0], X[1], ..., X[K-1].
  • O argumento s é uma string em que cada caractere é 0 ou 1, representando a string enviada por Aoi a Bitaro.

Dentro de Bitaro.cpp, seu programa pode chamar a seguinte função.

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

  Na chamada de número $j+1$ ($0\le j\le Q-1$) a esta função, você deve informar um caminho mínimo da cidade $0$ até a cidade $T_j$, alvo do plano de investigação $j$.

  • O parâmetro e é um vetor que representa o caminho mínimo da cidade $0$ até a cidade $T_j$.
  • Seja $n$ o comprimento do vetor e. Os elementos e[0], e[1], ..., e[n-1] são os índices das estradas do caminho mínimo da cidade $0$ até a cidade $T_j$, na ordem em que são percorridas.
  • Se houver vários caminhos mínimos possíveis, qualquer um deles pode ser escolhido como resposta.
  • Cada elemento do parâmetro e deve estar entre $0$ e $M-1$. Se essa condição não for satisfeita, seu programa receberá o veredito Wrong Answer [3].

  • A sequência de estradas indicada pelo argumento e deve formar um caminho da cidade $0$ até a cidade $T_j$. Formalmente, deve satisfazer as seguintes condições.

    Existe uma sequência de números $u_0,u_1,\ldots,u_n$ tal que:

    • $u_0=0$.
    • $u_n=T_j$.
    • A estrada e[k] ($0\le k\le n-1$) conecta as cidades $u_k$ e $u_{k+1}$.

    Se essas condições não forem satisfeitas, seu programa receberá o veredito Wrong Answer [4].

  • Se a sequência de estradas indicada pelo argumento e não for um caminho mínimo da cidade $0$ até a cidade $T_j$ entre todos os caminhos que começam na cidade $0$ e terminam na cidade $T_j$, seu programa receberá o veredito Wrong Answer [5]. Aqui, o comprimento do caminho é definido como a soma dos comprimentos das estradas utilizadas.
  • A função answer deve ser chamada exatamente $Q$ vezes. Se o número de chamadas a answer não for igual a $Q$ ao final da execução de bitaro, seu programa receberá o veredito Wrong Answer [6].

Observações importantes

• Seu programa pode implementar outras funções para uso interno ou usar variáveis globais. Os arquivos enviados serão compilados com o avaliador em um único executável. Todas as variáveis globais e funções internas devem ser declaradas em um namespace sem nome para evitar conflitos com outros arquivos. Na avaliação, o programa será executado como dois processos, de Aoi e de Bitaro. Os processos de Aoi e de Bitaro não podem compartilhar variáveis globais.
• Seu programa não deve usar a entrada padrão nem a saída padrão. Seu programa não deve se comunicar com outros arquivos de nenhuma maneira. Entretanto, pode escrever informações de depuração na saída de erro padrão.

Compilação e execução de teste

Você pode baixar, da página da competição, um arquivo compactado que contém o avaliador de exemplo para testar seu programa. O arquivo também contém um exemplo de código-fonte do seu programa.

O avaliador de exemplo está no arquivo grader.cpp. Para testar seu programa, coloque grader.cpp, Aoi.cpp, Bitaro.cpp, Aoi.h, Bitaro.h no mesmo diretório e execute o comando a seguir para compilar seus programas. Como alternativa, execute compile.sh, incluído no arquivo compactado.

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

Se a compilação for bem-sucedida, será gerado o executável grader.

O avaliador real é diferente do avaliador de exemplo. O avaliador de exemplo é executado como um único processo, que lê os dados da entrada padrão e escreve os resultados na saída padrão e na saída de erro padrão.

Entrada do avaliador de exemplo

O avaliador de exemplo lê os seguintes dados da entrada padrão.

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

Saída do avaliador de exemplo

O avaliador de exemplo escreve as seguintes informações na saída padrão e na saída de erro padrão (aspas usadas para clareza).

• Se seu programa receber o veredito Wrong Answer [1], [2], [3], [4] ou [6], o avaliador de exemplo escreve seu tipo, como Wrong Answer [1], na saída de erro padrão. Nada será escrito na saída padrão.
• Caso contrário, o comprimento da string $s$ retornada por aoi será escrito na saída de erro padrão no formato Accepted: 2024. Além disso, o comprimento do caminho informado na chamada de número $j+1$ ($0\le j\le Q-1$) à função answer será escrito na linha de número $j+1$ da saída padrão. O avaliador de exemplo não verifica se o caminho é mínimo.

Se seu programa satisfizer as condições de vários tipos de Wrong Answer, o avaliador de exemplo relata apenas um deles.

Restrições

Todos os dados de entrada satisfazem as seguintes condições:

• $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$).
• É possível viajar de qualquer cidade para qualquer outra percorrendo algumas estradas.
• Todos os valores de entrada são inteiros.

Pontuação

Se seu programa receber qualquer veredito Wrong Answer [1]–[6] (veja Detalhes de implementação) ou qualquer erro de execução (TLE (Time Limit Exceeded), MLE (Memory Limit Exceeded), Abnormal End etc.) em algum caso de teste, sua pontuação será de 0 pontos.

Caso contrário, a pontuação é baseada no comprimento máximo da string $s$ retornada pela função aoi entre todos os casos de teste desta tarefa, denotado por $L$.

• Se $1561\le L\le 12\,000$, a pontuação é $\left\lfloor\dfrac{100\,000}{L-560}\right\rfloor$ pontos.
• Se $0\le L\le 1560$, a pontuação é $100$ pontos.

Aqui, $\lfloor x\rfloor$ representa o maior inteiro que não é maior que $x$.

Exemplo de comunicação

A seguir estão uma entrada de exemplo para o avaliador de exemplo e as chamadas de função correspondentes.

Entrada 1

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

Exemplos de chamadas de função

O caminho mínimo da cidade $0$ até a cidade $1$ pode ser obtido percorrendo as estradas 1 e 0, nessa ordem, ou apenas a estrada 2. Portanto, na segunda chamada a answer neste exemplo, também é aceitável chamar answer([2]).

O arquivo sample-01-in.txt, que pode ser baixado da página da competição, corresponde ao exemplo de entrada 1.

Os arquivos sample-01-in.txt e sample-02-in.txt, incluídos nos arquivos disponíveis para download na página da competição, podem ser usados como entrada para o avaliador de exemplo.