Carrera de Relevos.


Submit solution

Points: 100 (partial)
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type
Allowed languages
C, C#, C++, Java, Python, VB

Las N (1 \leq N \leq 1,000) vacas convenientemente numeradas 1..N están competiendo en una carrera de relevos durante la cual varias vacas pueden correr simultáneamente.

Antes del tiempo t=0, cada vaca está en la línea de arranque, esperando a que sea su turno de correr una vuelta alrededor de la pista.

En el tiempo t=0, la vaca 1 comienza a correr alrededor de la pista y cruza la línea de arranque exactamente L_1 segundos después. En general, el tiempo que se demora corriendo una vuelta la vaca i es L_i (1 \leq L_i \leq 1,000). Tan pronto como ella cruce de vuelta la línea de arranque, ella señala M_1 otras vacas numeradas A_ij para que empiecen a correr inmediatamente. Generalmente la vaca i señala M_i vacas (0 \leq M_i \leq N) numeradas A_ij (1 \leq j \leq M_i) para quecomiencen a correr. Tarde o temprano, cada vaca es señalada al menos una vez. Algunas veces M_i podría ser 0 y no existen ninguna A_{ij}.

Cada una de las vacas señaladas comienza a correr y ejecuta el procedimiento de señalar cuando cruza la línea de arranque. Varias vacas podrían señalar a la misma vaca, pero cada vaca quiere correr únicamente una sola vuelta, por lo tanto las señales después de la primera son ignoradas.

El Granjero Juan quiere que usted determine el tiempo total de la carrera (esto es cuánto tiempo toma para que la vaca final complete su vuelta).

Considere una carrera pequeña con 5 vacas. La tabla a continuación muestra la identificación de la vaca (i), el tiempo que le toma correr una sola vuelta (L_i), el número de señales que la vaca i ejecutará cuando ella termine (M_i) y la lista (potencialmente vacía) de vacas a ser señaladas (A_{ij}):

i   L_i  M_i   A_i
1    4    2    2 4
2    3    3    1 3 4
3    7    1    5
4    4    2    3 5
5    1    0

Comenzando con la vaca 1 en el tiempo 0 produce esta serie de eventos:

TIEMPO      Evento
  0     La vaca 1 comienza a correr
  4     La vaca 1 termina; señala a 2 y a 4
  4     La vaca 2 comienza a correr (tiempo para terminar: +3 segundos-> 7)
  4     La vaca 4 comienza a correr (tiempo para terminar: +4 segundos-> 7)
  7     La vaca 2 termina; señala a  1, 3, y 4
  7     Las vacas  1 y 4 ignoran la señal duplicada
  7     La vaca 3 comienza a correr (tiempo para terminar :+7 segundos-> 14)
  8     La vaca 4 termina; señala a 3 y a 5
  8     La vaca 3 ignora la señal duplicada
  8     La vaca 5 comienza a correr (tiempo para terminar: +1 segundo-> 9)
  9     La vaca 5 termina, pero no tiene vacas a quienes señalar
 14     La vaca 3 termina, señala a 5
 14     La vaca 5 ignora la señal duplicada
 14     Todas las vacas terminan

Entrada

  • Línea 1: Un solo entero: N.
  • Líneas 2..N+1: La línea i+1 contiene varios enteros separados por espacios: L_i, M_i y luego M_i enteros A_ij.

Ejemplo de Entrada

5
4 2 2 4
3 3 1 3 4
7 1 5
4 2 3 5
1 0

Salida

  • Línea 1: Un solo entero, el tiempo en que la última vaca termina.

Ejemplo de Salida

14

Comments

There are no comments at the moment.