| Fişierul intrare/ieşire: | dominouri.in, dominouri.out | Sursă | Tiberiu Popoviciu 2011, Clasele 11-12 |
| Autor | Perticas Catalin | Adăugată de |  perticas catalin •perticas_catalin |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dominouri
Pe o tablă sunt N dominouri. Acestea sunt aşezate sub forma unui arbore. Dacă unele piese de domino sunt lovite cu o forţă destul de mare, ele vor cădea peste o altă piesă (excepţie face piesa 1 care nu cade peste alte piese). Pentru fiecare piesă de domino de pe tablă se cunoaşte câte alte piese trebuie să cadă peste ea pentru a cădea la rândul său, dar şi care sunt piesele care pot să cadă peste aceasta. Mitruţ tocmai a descoperit tabla cu dominouri şi se întreabă care e numărul minim de piese pe care trebuie să le doboare el pentru a face piesa 1 să cadă. Fiindcă Mitruţ are reguli stricte legate de arbori, el îşi dă voie să doboare doar piesele peste care nu are cine să cadă (frunzele din arbore).
Cerinţă
Răspundeţi la întrebarea lui Mitruţ.
Date de intrare
Fişierul de intrare dominouri.in conţine pe prima linie numărul N. Pe următoarele N linii se află câte un număr Ci (1 ≤ i ≤ N).reprezentând câte piese pot să cadă peste piesa i, urmat de Ci numere-indicele pieselor care dacă sunt lovite cad peste piesa i. Ultima linie din fişier conţine N numere naturale Fi(1 ≤ i ≤ N). Fi reprezintă numărul de piese care trebuie sa cadă pe dominoul i ca acesta să cadă şi el la rândul său. Frunzele din arbore au acest număr egal cu zero.
Date de ieşire
Fişierul de ieşire dominouri.out conţine pe prima linie un singur număr natural reprezentând răspunsul la întrebarea lui Mitruţ.
Restricţii
- 1 ≤ N ≤ 100 000
- Fi este întotdeauna mai mic sau egal cu numărul de fii ai nodului(piesei) i.
- Pentru toate nodurile terminale din arbore Fi = 0.
Exemplu
| dominouri.in | dominouri.out |
|---|---|
| 10 3 2 3 4 2 5 6 1 7 3 8 9 10 0 0 0 0 0 0 2 1 1 2 0 0 0 0 0 0 | 2 |
Explicaţie
Sunt de ajuns două piese pentru a doborâ dominoul 1. Acestea sunt ori 5 şi 7 ori 6 şi 7. Dominoul 7 este folosit pentru răsturnarea lui 3, în timp ce piesa 5 este folosită pentru răsturnarea lui 2. Piesele care fac ca 1 să cadă efectiv sunt 2 şi 3.
