Fişierul intrare/ieşire:	brperm.in, brperm.out	Sursă	RMI 2020 Ziua 1
Autor	Tamio-Vesa Nakajima	Adăugată de	Mihai-Cristian Popescu •mihai50000
Timp execuţie pe test	1 sec	Limită de memorie	256000 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Brperm

Editorialul

SE DA UN ARBORE...

Poveste şi cerinţă...

Am considerat ca sunt date anumite queryuri in input, daca secventa cutare e sau nu br-palindrom. Desigur, putem schimba formatul asta in varianta originala, in caz ca devine inutila schimbarea.

Queryurile sunt doar pe lantul catre radacina - nu vrem lca-uri si alte nebunii

Date de intrare

Fişierul de intrare brperm.in contine pe primul rand numarul N de noduri.
Al doilea rand contine cate N - 1 numere, iar al i-lea este tatal nodului i in arbore (retineti ca nodul 0 este radacina). Se garanteaza ca tatal unui nod are indicele mai mic ca el.
Al treilea rand contine un sir de N - 1 caractere, din care al i-lea caracter este caracterul pe muchia dintre i si tatal sau.
Al patrulea rand contine valorile Q X₁ Y₁ a b c d.

Date de ieşire

În fişierul de ieşire brperm.out se afiseaza numerele X_Q+1 Y_Q+1. Acestea se definesc dupa recurentele urmatoare:

A_i = X_i mod N
B_i = Y_i mod log₂(lungimea lantului de la A_i la radacina)
R_i = 1 daca lantul de lungime 2^B_i de la A_i insrep radacina este br-permutare, 0 altfel.
X_i+1 = (i + X_i + R_i) * a + b mod 1.000.000.007
Y_i+1 = (i + Y_i + R_i) * c + d mod 1.000.000.007

Restricţii

• SIGMA = 26

• ... ≤ ... ≤ ...

• Subtask1 (10 puncte): O(Q * N * logN) && NU neaparat linie
• Subtask2 (10 puncte): O(N * logN + Q * N) && NU neaparat linie
• Subtask3 (10 puncte): O(N * logN + Q) && linie && SIGMA = 2 && biased random (comisia a ales, pt fiecare test, cate un numar real p intre 0 si 1 iar fiecare caracter este 'a' cu probabilitate p si 'b' cu probabilitate 1-p)
• Subtask4 (30 puncte): O((N + Q) * logN * logN) sau O((N + Q) * sqrt(N + Q) + Q) (nu cunosc solutie, dar cine stie?) - anulat si inghitit de subtaskul urmator in caz ca nu dam queryuri
• Subtask5 (10 puncte): O(N * logN * logN + Q) - acelasi lucru ca subtaskul urmator daca nu dam queryuri
• Subtask6 (10 puncte): O((N + Q) * logN) - in caz ca exista
• Subtask7 (20 puncte): O(N * logN + Q) - in caz ca exista, altfel punctele merg la ultimul subtask existent

Exemplu

Explicaţie

...

Cum se trimit solutii?