Colegiul Național “Frații Buzești”
Centrul de Pregătire pentru Performanță în Informatică
InfoCNFB - Ediția a II-a, Seniori
9 decembrie 2023
Cerință
Se dă un număr egal cu sau .
Se dă în continuare un graf cu noduri care are structura unei păduri de arbori cu radacină. Aceasta este reprezentată printr-un vector de tați astfel:
- , dacă nodul curent este rădăcina unui arbore din pădure;
- , dacă nodul nu este radacină.
Pe această pădure de arbori se vor executa operații de urmatoarea formă:
(ATENȚIE, valorile și/sau , acolo unde este cazul, nu se vor citi explicit, ci ele trebuie calculate conform unei formule bazate atât pe valorile , și/sau , cât și pe răspunsul la ultima întrebare, așa cum este explicat mai jos).
1 coef_x coef_y
- devine (se garantează că în urma acestei operații graful va continua să aibă forma unei păduri de arbori);2 coef_x
- se va afișa numărul de noduri de pe lanțul de la nodul la rădăcina arborelui din care face parte ;3 coef_x
- se va afișa dimensiunea (ca număr de noduri) a arborelui din care face parte nodul ;4
- se va afișa dimensiunea celui mai mare arbore din pădure;5 coef_x coef_y
- se va afișa dacă și fac parte din același arbore, altfel se va afișa .
Formula de generare a lui x
și/sau y
în funcție de T
, coef_x
, coef_y
:
- :
x = coef_x
;y = coef_y
. - :
- Fie răspunsul la ultima întrebare de tip , , sau (inițial );
x = coef_x ^ p
;y = coef_y ^ p
(am notat prin^
operatia XOR pe biți între două valori);- Daca query-ul curent este de tipul , , sau , atunci
p
va deveni răspunsul la acest query.
Date de intrare
Pe prima linie a fișierului harb.in
se află numărul . Pe următoarea linie se află un număr .
Pe următoarea linie se află numere reprezentând elementele vectorului .
Pe următoarea linie se află reprezentând numărul de operații la care trebuie să se răspundă.
Urmează linii care vor descrie cele operații, câte una pe fiecare linie.
Date de ieșire
În fișierul harb.out
se vor scrie pe câte o linie răspunsul la fiecare întrebare de tip , , sau .
Restricții și precizări
# | Punctaj | Restricții |
---|---|---|
1 | 5 | ; , se garantează că există numai operații de tip sau , respectiv în orice moment de timp există un singur nod x cu parent[x] = x . |
2 | 5 | ; , se garantează că există numai operații de tip sau |
3 | 5 | ; , se garantează că există numai operații de tip , , sau |
4 | 10 | ; |
5 | 10 | ; , se garantează că există numai operații de tipul , sau |
6 | 10 | ; , se garantează că există numai operații de tipul , , sau |
7 | 35 | ; , se garantează că există numai operații de tipul , , sau |
8 | 10 | ; |
9 | 10 | ; |
Exemplul 1
harb.in
1
14
1 1 1 2 3 3 7 8 8 8 8 11 11 13
20
5 4 6
5 6 5
5 12 14
2 11
2 4
3 11
3 4
4
2 14
1 13 2
1 3 7
1 7 9
2 6
5 5 6
3 6
3 14
5 14 4
4
2 12
2 13
harb.out
1
3
11
2
3
7
6
7
4
5
3
9
5
2
9
3
3
Explicație
Pădurea inițială de arbori arată ca în figura de mai jos:
, , lungimea lanțului de la la este , arborele care îl conține pe are noduri, cel care îl conține pe are noduri, iar pentru query-ul de tip , cel mai mare arbore are noduri, etc.
În urma celor operații de modificare a părinților, pădurea de arbori va arăta așa:
, , arborele care îl conține pe are noduri, iar cel care îl conține pe are noduri, lanțul de la nodul la nodul are lungimea , etc.
Exemplul 2
harb.in
2
14
1 1 1 2 3 3 7 8 8 8 8 11 11 13
20
5 4 6
5 7 4
5 15 13
2 0
2 6
3 8
3 3
4
2 9
1 9 6
1 7 3
1 3 13
2 2
5 0 3
3 5
3 7
5 11 1
4
2 5
2 14
harb.out
1
3
11
2
3
7
6
7
4
5
3
9
5
2
9
3
3
Explicație
Acest exemplu este identic cu primul, singura diferență fiind faptul că inputul este dat conform formulelor pentru .