OMG P15010


Statement
 

pdf   zip

thehtml

¡OMG, es superfuerte! ¡Salía de la disco cuando de repente vi a Johnny con bambas negras y calcetines blancos! Es tan fuerte que ahora mismo voy a enviar un SMS a todos mis amigos. Además, sé que la primera cosa que van a hacer ellos al despertarse será enviar un SMS a todos sus amigos, etc. ¿A qué hora recibirá el propio Johnny un SMS con la noticia?

Entrada

Cada entrada contiene un único caso de pruebas. La primera línea contiene el número n de personas involucradas. La persona 1 soy yo, y la persona n es Johnny. A continuación, se dan n−1 líneas. La i-ésima de estas líneas contiene: el número i, el carácter “:”, un espacio, el instante de tiempo ti≥ 0 en el que se despertará la persona i-ésima, dos espacios, y los números de los amigos de la persona i-ésima, separados por espacios. Ninguna persona tendrá más de 25 amigos. Podría ocurrir que dos personas no fueran amigos mutuos (o sea, que a fuera amigo de b, pero b no lo fuera de a: cuando a se enterara de la noticia se lo diría a b, pero no al revés). Por último, siempre se tiene que t1=0.

Salida

Una línea con un único entero: el instante de tiempo en el que Johnny recibirá un SMS con la noticia. Si Johnny no llegara a enterarse nunca, escribe −1.

Puntuación

Hay 10 grupos de entradas. Se obtendrán 10 puntos por cada grupo de entradas resuelto correctamente, tardando no más de 1 segundo de CPU por cada entrada del grupo. Las entradas del grupo i-ésimo contendrán situaciones con no más de 3, 5, 8, 15, 30, 100, 300, 1000, 3000 y 10000 personas en total.

Public test cases
  • Input

    3
    1: 0  2
    2: 10  1 3
    

    Output

    10
    
  • Input

    5
    1: 0  2
    2: 5  3 4
    3: 10  5
    4: 6  5
    

    Output

    6
    
  • Input

    6
    1: 0  2 3 6
    2: 134  4 5
    3: 87  1 2 5
    4: 98  2 3 6 
    5: 99  6 3 4
    

    Output

    0
    
  • Input

    6
    1: 0  2 3
    2: 134  4 5
    3: 87  1 2 5
    4: 98  2 3 6 
    5: 99  6 3 4
    

    Output

    99
    
  • Input

    2
    1: 0
    

    Output

    -1
    
  • Input

    4
    1: 0  2
    2: 10  3
    3: 10  4
    

    Output

    10
    
  • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++