Revizia anterioară Revizia următoare
| 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
- Arbore (graf neorientat conex si aciclic) cu N noduri
- Arbore binar (fiecare nod are cel putin 0 fii si cel mult doi fii)
- Arbore inradacinat in nodul 1
Cati subarbori exista cu proprietatea ca orice nod am alege din acel subarbore, nodul respectiv are prioritatea mai mare sau egala cu a fiilor sai si cheia acelui nod este mai mare sau egala cu a unuia dintre fii daca acel fiu exista si mai mica strict decat a celuilalt fiu daca acesta exista ?
De la Ceterchi citire:
Un arbore binar de căutare este un arbore binar cu următoarele proprietăţi:
- fiecare nod are o valoare asociată;
- pentru fiecare nod, subarborele stâng conţine valori mai mici sau egale decât cea a nodului, iar cel drept conţine valori mai mari sau egale decât cea a nodului
- fiecare nod are prioritatea mai mare sau egala cu cea a fiilor sai (+ 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. Urmatoarea linie va contine alte N numere, al i-lea dintre ele fiind PRIOi.
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
#Comisia nu putea lasa sa treaca o noua editie a A.G.M. fara sa dea o problema cu treapuri
Un subarbore inradacinat intr-un nod care nu are fii, este considerat frunza
Exemplu
| treap.in | treap.out |
|---|---|
| 3 1 2 1 3 5 5 7 100 9 1 | 1 1 1 |
| 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 |
Explicaţie
...
