En la fábrica de JOI Co., Ltd. hay $N$ mesas, numeradas del $0$ al $N-1$. También hay $N-1$ cintas transportadoras, numeradas del $0$ al $N-2$. La cinta transportadora $i$ ($0\le i\le N-2$) conecta las mesas $A_i$ y $B_i$. Transporta productos de una mesa a la otra, pero no podemos ver el sentido del transporte. Si ignoramos los sentidos de las cintas, cualquier par de mesas está conectado por una sucesión de cintas transportadoras.

IOI-kun es el director de la fábrica. Como ha olvidado el sentido del transporte de todas las cintas, realizará varias veces la siguiente secuencia de operaciones.

1. Elige algunas cintas transportadoras e invierte sus sentidos de transporte.
2. Elige algunas mesas y coloca un producto en cada una.

3. Para cada mesa en la que se ha colocado un producto, ocurre simultáneamente una de las siguientes cosas.

   • Si no hay ninguna cinta que transporte productos desde ella, no ocurre nada.
   • Si hay cintas que transportan productos desde ella, una de ellas transporta el producto de esa mesa. El producto se detiene en la mesa de destino de la cinta y ya no se mueve más.

4. IOI-kun comprueba si hay uno o más productos en cada mesa. Si una mesa tiene productos, los retira todos.

5. Para cada cinta cuyo sentido se invirtió en la operación 1, IOI-kun vuelve a invertirlo, de modo que recupera su sentido original.

IOI-kun quiere determinar el sentido original de cada cinta realizando la secuencia anterior como máximo 30 veces.

Dada la información sobre las mesas conectadas por las cintas, escribe un programa que implemente la estrategia de IOI-kun para determinar el sentido original de cada cinta realizando la secuencia anterior como máximo 30 veces.

Detalles de implementación

Debes enviar un archivo.

El archivo es conveyor.cpp. Debe implementar la siguiente función. El programa debe incluir conveyor.h mediante la directiva de preprocesamiento #include.

En conveyor.cpp debes implementar la siguiente función.

• void Solve(int N, std::vector<int> A, std::vector<int> B)

  Esta función se llama una sola vez por caso de prueba.

  • El parámetro N es el número de mesas $N$.
  • Los parámetros A, B son vectores de longitud $N-1$ que describen las mesas conectadas por las cintas.

Tu programa puede llamar a las siguientes funciones.

• std::vector<int> Query(std::vector<int> x, std::vector<int> y)

  Mediante esta función, IOI-kun realiza las operaciones en la fábrica.

  • El parámetro x es un vector de longitud $N-1$. Para $0\le i\le N-2$, IOI-kun invierte el sentido de la cinta $i$ si x[i] = 1, y no lo invierte si x[i] = 0.
  • El parámetro y es un vector de longitud $N$. Para $0\le j\le N-1$, IOI-kun coloca un producto en la mesa $j$ si y[j] = 1, y no coloca ninguno si y[j] = 0.
  • Sea z el valor devuelto por esta función. Es un vector de longitud $N$. Para $0\le j\le N-1$, hay uno o más productos en la mesa $j$ si z[j] = 1, y no hay ninguno si z[j] = 0.
  • La longitud del vector x debe ser $N-1$. Si no se cumple esta condición, tu programa recibirá el veredicto Wrong Answer [1].
  • Cada elemento del vector x debe ser $0$ o $1$. Si no se cumple esta condición, tu programa recibirá el veredicto Wrong Answer [2].
  • La longitud del vector y debe ser $N$. Si no se cumple esta condición, tu programa recibirá el veredicto Wrong Answer [3].
  • Cada elemento del vector y debe ser $0$ o $1$. Si no se cumple esta condición, tu programa recibirá el veredicto Wrong Answer [4].
  • No debes llamar a Query más de 30 veces. Si lo haces, tu programa recibirá el veredicto Wrong Answer [5].

• void Answer(std::vector<int> a)

  Mediante esta función, IOI-kun comunica el sentido original de cada cinta.

  • El parámetro a es un vector de longitud $N-1$. Para $0\le i\le N-2$, la cinta $i$ transporta productos de $A_i$ a $B_i$ si a[i] = 0, y de $B_i$ a $A_i$ si a[i] = 1.
  • La longitud del vector a debe ser $N-1$. Si no se cumple esta condición, tu programa recibirá el veredicto Wrong Answer [6].
  • Cada elemento del vector a debe ser $0$ o $1$. Si no se cumple esta condición, tu programa recibirá el veredicto Wrong Answer [7].
  • Si IOI-kun comunica un sentido incorrecto para alguna cinta, tu programa recibirá el veredicto Wrong Answer [8].
  • Debes llamar a Answer exactamente una vez. Si llamas a Answer más de una vez, tu programa recibirá el veredicto Wrong Answer [9]. Si al terminar Solve no has llamado a Answer, tu programa recibirá el veredicto Wrong Answer [10].

Avisos importantes

• Tu programa puede implementar otras funciones para uso interno o utilizar variables globales.
• Tu programa no debe utilizar la entrada ni la salida estándar. Tampoco debe comunicarse con otros archivos por ningún medio. Sin embargo, puede escribir información de depuración en la salida de error estándar.

Compilación y ejecución de prueba

Puedes descargar de la página del concurso un archivo comprimido que contiene el evaluador de ejemplo para probar tu programa. El archivo también contiene un archivo fuente de ejemplo para tu programa.

El evaluador de ejemplo es el archivo grader.cpp. Para probar tu programa, coloca grader.cpp, conveyor.cpp y conveyor.h en el mismo directorio y ejecuta el siguiente comando para compilar los programas. También puedes ejecutar compile.sh, incluido en el archivo comprimido.

g++ -std=gnu++17 -O2 -o grader grader.cpp conveyor.cpp

Si la compilación tiene éxito, se genera el ejecutable grader.

Ten en cuenta que el evaluador real es distinto del evaluador de ejemplo. El evaluador de ejemplo se ejecuta como un único proceso que lee los datos de la entrada estándar y escribe los resultados en la salida estándar.

Entrada del evaluador de ejemplo

El evaluador de ejemplo lee los siguientes datos de la entrada estándar.

$$ \begin{array}{l} N \\ A_0\ A_1\ \cdots\ A_{N-2} \\ B_0\ B_1\ \cdots\ B_{N-2} \\ C_0\ C_1\ \cdots\ C_{N-2} \end{array} $$

Para $0\le i\le N-2$, $C_i=0$ si la cinta $i$ transporta productos de la mesa $A_i$ a la mesa $B_i$. En caso contrario, $C_i=1$.

Salida del evaluador de ejemplo

El evaluador de ejemplo escribe la siguiente información en la salida estándar (las comillas se incluyen por claridad).

• Si tu programa se considera correcto, comunica el número de llamadas a Query como «Accepted: 22».
• Si tu programa recibe algún tipo de Wrong Answer, el evaluador de ejemplo escribe su tipo, como «Wrong Answer [4]».

Si tu programa cumple las condiciones de varios tipos de Wrong Answer, el evaluador de ejemplo solo comunica uno de ellos.

En el evaluador de ejemplo, entre las cintas que transportan productos desde la mesa en la que se ha colocado un producto, la cinta que lo transporta se elige uniformemente al azar mediante números pseudoaleatorios cuyos resultados no cambian entre ejecuciones. Para cambiar la semilla de los números pseudoaleatorios, ejecuta el evaluador de ejemplo con un primer argumento entero de la siguiente manera.

./grader 2023

Avisos sobre la evaluación

En algunos casos de prueba, el evaluador real es adaptativo. Esto significa que no tiene una respuesta fija al principio y que responde según las llamadas anteriores a Query. Se garantiza que existe al menos una respuesta compatible con todas las respuestas del evaluador.

Restricciones

Todos los datos de entrada satisfacen las siguientes condiciones.

• $0\le A_i\le N-1$ ($0\le i\le N-2$).
• $0\le B_i\le N-1$ ($0\le i\le N-2$).
• Si ignoramos los sentidos de las cintas, cualquier par de mesas está conectado por una sucesión de cintas transportadoras.

Subtareas

1. (1 punto) $N=2$.
2. (14 puntos) $N=30$.
3. (10 puntos) $N=100\,000$, $A_i=i$ ($0\le i\le N-2$), $B_i=i+1$ ($0\le i\le N-2$).
4. (75 puntos) $N=100\,000$.

Ejemplo de comunicación

A continuación se muestra una entrada de ejemplo para el evaluador de ejemplo y las llamadas a funciones correspondientes.

Entrada 1

3
0 2
2 1
1 0

Llamadas a funciones de ejemplo

Para la primera llamada a Query, otro valor devuelto posible, además de [1, 0, 0], es [0, 1, 0].

En la segunda llamada a Query, el producto de la mesa $0$ se transporta a la mesa $2$ por la cinta $0$ y se detiene allí. Ten en cuenta que este producto no se transportará a la mesa $1$ por la cinta $1$.

Ten en cuenta que esta entrada de ejemplo no satisface las restricciones de ninguna subtarea.

Entre los archivos que se pueden obtener de la página del concurso, sample-02.txt satisface las restricciones de la subtarea 1 y sample-03.txt satisface las restricciones de la subtarea 2.