| Fişierul intrare/ieşire: | treap.in, treap.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 17 |
| Autor | Patrick Sava | Adăugată de |  AGMInformatica •AGMinformatica |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Treap
Undeva intr-un univers paralel, Piromanul a ajuns sa iubeasca apa si nu focul ca de obicei. Totusi, nu s-a schimbat prea mult... inca ii plac treapurile, ca in problema Metro . Gandindu-se ca comisia A.G.M s-ar face de ras daca ar lasa sa treaca cea de-a treia editie fara o problema cu treapuri, s-a gandit sa aibe grija de imaginea tuturor colegilor sai.
Piro, baiat fin de altfel, nu isi doreste sa fie chiar cel mai antipatizat membru al comisiei, asa ca va face o scurta incursiune impreuna cu voi in ceea ce inseamna tainele treap-ului.
Un arbore este un graf neorientat conex si aciclic.
Un arbore inradacinat este un arbore care are radacina fixata.
Un arbore binar este un arbore cu proprietatea ca fiecare nod din componenta sa are cel mult doi fii.
Un arbore binar de cautare este un arbore binar cu urmatoarele proprietati:
-fiecare nod are o valoare asociata
-pentru fiecare nod, subarborele stang contine valori mai mici sau egale decat cea a nodului, iar cel drept contine valori mai mari strict decat cea a nodului
Un max-heap este un arbore binar cu proprietatea ca fiecare nod are o valoare asociata si, in plus, valoarea asociata unui nod este mai mare sau egala cu cea asociata fiilor sai.
Un treap este un arbore cu proprietatea ca fiecare nod are asociat doua valori : cheie si prioritate. Daca ne uitam doar la cheile nodurilor, facand abstractie de prioritati, atunci acesta este arbore binar de cautare. Daca ne uitam la prioritatile nodurilor, facand abstractie de chei, atunci acesta este max-heap.
Dandu-vi-se un arbore binar cu N noduri, inradacinat in nodul 1, trebuie sa determintati care subarbori au proprietatea de treap.
Date de intrare
Fişierul de intrare treap.in va contine pe prima linie numarul N. Urmatoarele N-1 linii vor contine perechi de cate 2 numere naturale x, y cu proprietatea ca exista muchie intre nodurile x si y in arbore. Urmatoarea linie va contine N numere, al i-lea dintre ele fiind KEYi (adica cheia nodului respectiv). Urmatoarea linie va contine alte N numere, al i-lea dintre ele fiind PRIOi (adica prioritatea nodului respectiv).
Date de ieşire
În fişierul de ieşire treap.out se va afisa un sir de N numere dupa cum urmeaza : al i-lea numar din sir va fi 1 daca subarborele inradacinat in nodul i are proprietatea de treap si 0 altfel. Numerele vor fi afisate cu spatii intre ele.
Restricţii
- 1 <= N <= 150.000
- 1 <= KEYi <= 109
- 1 <= PRIOi <= 109
- Arborele se considera ca este inradacinat in nodul 1
- La finalul fisierului de iesire este '\n', nu spatiu
- Un subarbore inradacinat intr-un nod care nu are fii, este considerat frunza si reprezinta evident un treap
- Nu se garanteaza ca prioritatile generate sunt aleatoare, treap-ul avand forme dintre cele mai diverse.
Exemplu
| treap.in | treap.out |
|---|---|
| 3 1 2 1 3 5 5 7 100 9 1 | 1 1 1 |
| treap.in | treap.out |
|---|---|
| 3 1 2 1 3 5 8 7 100 9 1 | 0 1 1 |
| treap.in | treap.out |
|---|---|
| 3 1 2 2 3 2 1 3 3 2 1 | 0 1 1 |
