Mansión Larga


Submit solution

Points: 100 (partial)
Time limit: 3.0s
Memory limit: 256M

Authors:
Problem types
Allowed languages
C, C++, Java, Pascal, Python, VB

Hay una mansión ancha con N habitaciones localizadas en filas desde el esta hacia el oeste. La i-ésima habitación desde es el este es llamada la habitación i. Para cada i tal que 1 \leq i \leq n - 1, la habitación i y la habitación i + 1 están conectadas por un corredor. Nosotros podemos pasar por los corredores en ambas direcciones. Necesitamos un llave para entrar en un corredor desde una habitación. Cada llave tiene un numero llamado tipo. Mas de una llave pueden tener el mismo tipo.

Desde la habitación i o la habitación i + 1, nosotros necesitamos una llave de tipo C_i para entrar a el corredor entre ellas. Hay B_i llaves en la habitación i. Sus tipos son A_{i,j} (1 \leq j \leq B_i). Si entras en una habitación, puedes coger todas sus llaves. Después de eso puede usarlas para entrar en los corredores.Puedes usar cada llave tantas veces como quieras. Algunas veces, obtienes varias llaves del mismo tipo pero no hay diferencia entre tener una o mas llaves del mismo tipo.

Para lidiar con la situación donde te pierdes en la mansión planeas escribir un programa donde responderás las siguientes pregunta:

  • Si te encuentras en la habitación x sin ninguna llave, puedes llegar a la habitación y?

Tu tareas es escribir un programa que responda a esas preguntas.

Tarea:

Dada la información de la mansión y las preguntas, escribir un programa que determine para cada pregunta cuando puedes moverte de una habitación a otra asumiendo que te encuentras en la mansión sin ninguna llave.

Entrada:

La primera linea de la entrada contiene un entero N, el número de habitación en la mansión.

La segunda linea de entrada contiene N - 1 enteros separados por espacio C_1, C_2, \dots, C_{N-1}. Esto significa que necesitas la llave de tipo C_i para entrar al corredor que conecta la habitación i y la habitación i + 1.

La i-ésima linea (1 \leq i \leq N) de las siguientes N lineas contiene un entero positivo B_i y B_i enteros separados por espacio A_{i,1}, A_{i,2}, \dots, A_{i,B_i}. Esto significa que en la habitación i hay B_i llaves y sus tipos son A_{i,j} (1 \leq j \leq B_i).

La siguiente línea contiene un entero Q, el número de preguntas.

La k-ésima línea (1 \leq k \leq Q) de las siguientes Q líneas contiene dos enteros separados por espacio X_k, Y_k, Esto significa que la k-ésima pregunta pregunta cuando puedes moverte de la habitación X_k a la habitación Y_k asumiendo que estás en la mansión sin ninguna llave.

Salida:

La salida consta de Q líneas. La k-ésima línea (1 \leq k \leq Q) de las Q lineas contiene YES si te puedes mover de la habitación X_k a la habitación Y_k asumiendo que el está ahora en la habitación X_k y no tiene llaves. En otro caso contiene NO.

Limites:

Todos los datos de entrada satisfacen las siguientes condiciones:

2 \leq N \leq 5 \cdot 10^5

1 \leq Q \leq 5 \cdot 10^5

1 \leq B_1 + B_2 + \dots + B_N \leq 5 \cdot 10^5

1 \leq B_i \leq N (1 \leq i \leq N)

1 \leq C_i \leq N (1 \leq i \leq N - 1)

1 \leq A_{i,j} \leq N (1 \leq i \leq N, 1 \leq j \leq B_i)

Los B_i enteros A_{i,1}, A_{i,2}, \dots, A_{i,B_i} son diferentes entre ellos (1 \leq i \leq N). 1 \leq X_k \leq N (1 <= k <= Q)

1 \leq Y_k \leq N (1 <= k <= Q)

X_k \ne Y_k (1 <= k <= Q)

Subtask 1 (5 puntos):

N <= 5000 Q <= 5000 B_1 + B_2 + ... + B_N \leq 5000

Subtask 2 (5 puntos).

N \leq 5000 B_1 + B_2 + ... + B_N \leq 5000

Subtask 3 (15 puntos):

N \leq 10^5

C_i \leq 20 (1 \leq i \leq N - 1)

A_{i,j} \leq 20 (1 \leq i \leq N, 1 \leq j \leq B_i)

Subtask 4 (75 puntos):

Sin restricciones adicionales.

Entrada de ejemplo 1:

5
1 2 3 4
2 2 3
1 1
1 1
1 3
1 4
4
2 4
4 2
1 5
5 3

Salida de ejemplo 1:

YES
NO
NO
YES

En la primera pregutna, si visitas las habitaciones 2, 1, 2, 3, 4 en ese orden, logras llegar a la habitacion 4.

En la segunda pregunta, solo puedes visitar las habitaciones 3 y 4.

El la tercera pregunta, no puedes obtener una llave de tipo 4 de la habitacion 5 a la 4. Por lo tanto no puedes llegar a la habitacion 5.

En la cuarta pregunta, si visitas las habitaciones 5, 4, 3 es ese orden, logras llegar a la habitacion 3.

Entrada de ejemplo 2:

5
2 3 1 3
1 3
1 2
1 1
1 3
1 2
4
1 3
3 1
4 3
2 5

Salida de ejemplo 2:

NO
YES
NO
YES

Entrada de ejemplo 3:

7
6 3 4 1 2 5
1 1
1 5
1 1
1 1
2 2 3
1 4
1 6
3
4 1
5 3
4 7

Salida de ejemplo 3:

YES
NO
YES

Comments

There are no comments at the moment.