OMG P15010
¡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.
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
- Author
- Omer Giménez
- Language
- Spanish
- Official solutions
- C++
- User solutions
- C++