Fişierul intrare/ieşire:prepost.in, prepost.outSursăad-hoc
AutorDin FolclorAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.2 secLimită de memorie4096 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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.inprepost.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 sa te autentifici pentru a trimite solutii. Click aici