Fișierul intrare/ieșire: prepost.in, prepost.out Sursă ad-hoc
Autor din folclor Adăugată de Catalin.FrancuCătălin Frâncu Catalin.Francu
Timp execuție pe test 0.2 sec Limită de memorie 4096 KB
Scorul tău N/A Dificultate normalnormalnormalnormalnormal

Vezi soluțiile trimise | Statistici

Prepost

Fie un arbore general cu rădăcină cu N noduri numerotate de la 1 la N. Se cunosc parcurgerile sale în preordine și în postordine, date sub forma a câte unui vector cu N elemente. Să se reconstituie muchiile arborelui, indicând pentru fiecare nod cine este părintele lui.

Date de intrare

Fișierul de intrare prepost.in conține pe prima linie numărul de noduri N. Pe a doua linie se găsește o permutare a mulțimii { 1, 2, …, N } indicând parcurgerea în preordine. Pe a treia linie se găsește o altă permutare a mulțimii { 1, 2, …, N } indicând parcurgerea în postordine.

Date de ieșire

În fișierul de ieșire prepost.out se vor tipări N numere. Al i-lea număr indică părintele nodului i. Pentru rădăcină se va tipări valoarea 0.

Restricții

  • 1 ≤ N ≤ 100.000

Exemplu

prepost.in prepost.out
8
4 3 1 5 7 8 6 2
3 5 7 1 2 6 8 4
4 6 4 0 1 8 1 4

Explicație

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii