Fişierul intrare/ieşire:bile7.in, bile7.outSursăSelectie echipe ACM ICPC, UPB 2009
AutorMugurel Ionut AndreicaAdăugată demugurelionutMugurel-Ionut Andreica mugurelionut
Timp execuţie pe test0.05 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Bile7

Se da un arbore cu N noduri, numerotate de la 1 la N. Radacina arborelui este nodul 1. In nodul P se afla o bila albastra. In fiecare din celelalte noduri se afla ori o bila rosie, ori nicio bila. Se doreste eliberarea tuturor nodurilor de pe drumul de la nodul P la radacina arborelui. Mai exact, trebuie sa mutam unele bile rosii, astfel incat in fiecare nod de pe drumul de la nodul P la nodul 1 (cu exceptia nodului P) sa nu se afle nicio bila. O mutare consta in a lua o bila rosie dintr-un nod x si a o amplasa intr-un nod y care este fiu al lui x, cu conditia ca nodul y sa fie liber (adica sa nu contina nicio bila, fie ea rosie sau albastra). Bila albastra nu se poate muta din nodul P.

Determinati numarul minim de mutari necesare pentru ca niciunul din nodurile de pe drumul de la nodul P la nodul 1 sa nu contina vreo bila rosie.

Date de intrare

Prima linie a fisierului bile7.in contine numerele intregi N, P si K. K reprezinta numarul total de bile rosii ce se afla in nodurile arborelui. Urmatoarele N linii descriu structura arborelui: a i-a dintre aceste linii contine numarul nfii(i), urmat de nfii(i) numere f1, ..., fnfii(i), avand semnificatia ca nodurile f1, ..., fnfii(i) sunt fiii nodului i. Ultima linie contine K numere intregi, reprezentand numerele nodurilor in care se afla cate o bila rosie. Toate numerele de pe aceeasi linie sunt separate prin cate un spatiu.

Date de ieşire

In fisierul de iesire bile7.out veti afisa numarul minim de mutari cerut. Daca nu exista nicio secventa de mutari care sa indeplineasca cerintele problemei, afisati numarul -1.

Restricţii

  • 1 ≤ N ≤ 5000
  • 1 ≤ P ≤ N
  • 1 ≤ K ≤ N-1

Exemplu

bile7.inbile7.out
8 5 3
1 3
1 7
2 2 4
2 5 6
0
0
1 8
0
2 3 7
2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?