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).
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. Q reprezinta numarul de query-uri.
Fie A_i al i-lea nod de query, si 2^B_i a i-a lungime de query. Fie R_i raspunsul la cel de al i-lea query: 1 daca si numai daca lantul de la A_i in sus de lungime 2^B_i este br-palindrom, 0 altfel. Acestea se calculeaza, impreuna cu X_i, dupa formulele:
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
A_i = X_i mod N
B_i = X_i mod log₂(lungimea lantului de la A_i la radacina)
Pentru a determina query-ul A_i+1 dandu-se query-ul A_i si raspunsul R la queryul acesta, se foloseste formula A_i+1 = (A_i + R) * U + V mod N.

Date de ieşire

În fişierul de ieşire brperm.out se afiseaza numarul A_Q+1.

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?