Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | infestation.in, infestation.out | Sursă | Shumen 2019 Seniori |
| Autor | Encho Mishinev | Adăugată de |  Matteo Verzotti •Matteoalexandru |
| Timp execuţie pe test | 0.75 sec | Limită de memorie | 131072 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Infestation
Vila Lorei este invadata de sobolani. Din fericire, putem descrie camerele din vila Lorei ca si un arbore cu radacina in nodul 1, care are N noduri. Initial, niciun nod nu este infectat. Mai multe evenimente se intampla consecutiv, fiecare dintre ele fiind unul din urmatoarele 4 tipuri:
- "1 X" - Nodul X devine infestat
- "2 X" - Lora vrea sa elimine soarecii din nodurile de pe lantul de la nodul 1 la nodul X (inclusiv) folosind ultrasunet pe toti simultan. Daca ultrasunetul este folosit pe un nod infestat, soarecii din el se imprastie, iar fiecare din vecinii sai directi, in care ultrasunetul nu este folosit la momentul actual, devine infestat. Nodurile in care folosim ultrasunetul se opresc din a fi infestate. Dupa ce soarecii s-au mutat, ultrasunetul este oprit, adica nodurile eliberate pot fi infestate din nou, in viitor.
- "3 X" - Lora angajeaza profesionisti care sa elibereze nodul X si copiii sai. In concluzie, X si toti succesorii sai directi nu mai sunt infectati.
- "4 X" - Lora doreste sa stie numarul total de noduri infestate din subarborele nodului X.
Subarborele nodului X este definit ca si setul de noduri care il contin pe X, precum si toti succesorii sai directi sau indirecti (vezi exemplul pentru mai multe informatii).
Date de intrare
Fişierul de intrare infestation.in va contine pe prima linie numarul natural N - numarul de noduri din arbore. A doua linie contine N - 1 numere, al i-lea fiind pi+1 - parintele nodului i + 1. A treia linie contine numarul de evenimente Q. Urmatoarele Q linii contin cate doua numere intregi, ce reprezinta cate un eveniment in una din formatele mentionate anterior.
Date de ieşire
În fişierul de ieşire infestation.out se va afisa pentru fiecare eveniment de tipul 4 cate un singur numar pe o linie - numarul de noduri infestate din subarbore.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| infestation.in | infestation.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
