Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pandemie.in, pandemie.out | Sursă | FMI No Stress 9 |
| Autor | Usurelu Florian Robert | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pandemie
Omenirea se confrunta cu o grava pandemie la nivel global din cauza virusului mielenevirus. Din aceasta pricina, Organizatia Entuziasta Internationala a Spitalelor (OEIS), a hotarat stabilirea unui centru medical in cel mai avansat stat, iGorj. Cele N state (numerotate de la 1 la N, iGorj fiind statul nr 1) la nivel mondial se pot reprezenta cu tot cu legaturile bidirectionale dintre ele sub forma unui arbore. Mielenevirusul este foarte imprevizibil: oamenii dintr-un stat X se pot vindeca instant sau se pot imbolnavi toti spontan. Vladuri isi pune Q intrebari de forma: 1 X (al X-lea stat este virusat), 2 X (al X-lea stat este vindecat) si 3 X (daca s-ar afla in al X-lea stat, care ar fi cel mai apropiat stat de iGorj, la care ar putea ajunge daca nu ar trece prin niciun stat virusat.
Ajutati-l pe Vladuri sa afle pentru fiecare intrebare de tipul 3, statul cu pricina.
Date de intrare
Fişierul de intrare pandemie.in va contine pe prima linie un numar N, iar pe urmatoarele N-1 linii cate 2 numere A si B reprezentand faptul ca exista o legatura intre al A-lea stat si al B-lea stat. Pe urmatoarea linie va contine un numar Q reprezentand numarul de intrebari de tipurile 1, 2 si 3 pe care si le va pune Vladuri. Pe urmatoarele Q linii se vor afla cate 2 numere O si S, O reprezentand tipul intrebarii, iar S reprentand statul asupra caruia este supusa intrebarea.
Date de ieşire
În fişierul de ieşire pandemie.out se vor afla pe cate o linie distincta, cate un numar reprezentand raspunsul pentru fiecare intrebare de tipul 3.
Restricţii
- PROPUN sa dam 4 teste pe N^2, 4 teste pe Nloglog si 2 teste cu Nlog. Bagam N maxim 100k si ajustam timpii
- 1 ≤ N, Q ≤ 50.000
- Pentru 20 de puncte (testele 1-2), 1 ≤ N, Q ≤ 1000
- Pentru alte 30 de puncte (testele 3-4-5), 1 ≤ N, Q ≤ 10.000
- Daca pentru o intrebare de tip 3 nu se poate pleca din nodul X inspre iGorj, se va afisa X.
- Se neglijeaza starea nodului X (virusat/ nevirusat) la intrebarile de tip 3.
Exemplu
| pandemie.in | pandemie.out |
|---|---|
| 7 1 2 1 3 2 4 2 6 2 7 4 5 7 3 5 1 1 1 3 3 6 3 3 2 3 3 3 | 1 2 3 3 |
