harb

Time limit: 2s Memory limit: 128MB Input: harb.in Output: harb.out

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 TT egal cu 11 sau 22.
Se dă în continuare un graf cu NN noduri care are structura unei păduri de arbori cu radacină. Aceasta este reprezentată printr-un vector de tați parent\text{parent} astfel:

  • parent[nod]=nod\text{parent}[\text{nod}] = \text{nod}, dacă nodul curent este rădăcina unui arbore din pădure;
  • parent[nod]=par\text{parent}[\text{nod}] = \text{par}, dacă nodul nu este radacină.

Pe această pădure de arbori se vor executa MM operații de urmatoarea formă:
(ATENȚIE, valorile xx și/sau yy, acolo unde este cazul, nu se vor citi explicit, ci ele trebuie calculate conform unei formule bazate atât pe valorile TT, coef_x\text{coef\_x} și/sau coef_y\text{coef\_y}, cât și pe răspunsul la ultima întrebare, așa cum este explicat mai jos).

  • 1 coef_x coef_y - parent[x]\text{parent}[x] devine yy (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 xx la rădăcina arborelui din care face parte xx;
  • 3 coef_x - se va afișa dimensiunea (ca număr de noduri) a arborelui din care face parte nodul xx;
  • 4 - se va afișa dimensiunea celui mai mare arbore din pădure;
  • 5 coef_x coef_y - se va afișa lca(x,y)\text{lca}(x, y) dacă xx și yy fac parte din același arbore, altfel se va afișa 00.

Formula de generare a lui x și/sau y în funcție de T, coef_x, coef_y:

  • T=1T = 1: x = coef_x; y = coef_y.
  • T=2T = 2:
    • Fie pp răspunsul la ultima întrebare de tip 22, 33, 44 sau 55 (inițial p=0p = 0);
    • 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 22, 33, 44 sau 55, atunci p va deveni răspunsul la acest query.

Date de intrare

Pe prima linie a fișierului harb.in se află numărul TT. Pe următoarea linie se află un număr NN.
Pe următoarea linie se află NN numere reprezentând elementele vectorului parent\text{parent}.
Pe următoarea linie se află MM reprezentând numărul de operații la care trebuie să se răspundă.
Urmează MM linii care vor descrie cele MM 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 22, 33, 44 sau 55.

Restricții și precizări

# Punctaj Restricții
1 5 T=1T = 1; N,M1 000N, M \leq 1 \ 000, se garantează că există numai operații de tip 11 sau 22, respectiv în orice moment de timp există un singur nod x cu parent[x] = x.
2 5 T=1T = 1; N,M1 000N, M \leq 1 \ 000, se garantează că există numai operații de tip 11 sau 22
3 5 T=1T = 1; N,M1 000N, M \leq 1 \ 000, se garantează că există numai operații de tip 11, 22, 33 sau 44
4 10 T=1T = 1; N,M1 000N, M \leq 1 \ 000
5 10 T=1T = 1; N,M100 000N, M \leq 100 \ 000, se garantează că există numai operații de tipul 22, 33 sau 44
6 10 T=1T = 1; N,M100 000N, M \leq 100 \ 000, se garantează că există numai operații de tipul 22, 33, 44 sau 55
7 35 T=1T = 1; N,M100 000N, M \leq 100 \ 000, se garantează că există numai operații de tipul 11, 22, 33 sau 44
8 10 T=1T = 1; N,M100 000N, M \leq 100 \ 000
9 10 T=2T = 2; N,M100 000N, M \leq 100 \ 000

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:

lca(4,6)=1\text{lca}(4, 6) = 1, lca(12,14)=11\text{lca}(12, 14) = 11, lungimea lanțului de la 44 la 11 este 33, arborele care îl conține pe 1111 are 77 noduri, cel care îl conține pe 44 are 66 noduri, iar pentru query-ul de tip 44, cel mai mare arbore are 77 noduri, etc.

În urma celor 33 operații de modificare a părinților, pădurea de arbori va arăta așa:

lca(14,4)=2\text{lca}(14, 4) = 2, lca(5,6)=3\text{lca}(5, 6) = 3, arborele care îl conține pe 66 are 99 noduri, iar cel care îl conține pe 1414 are 55 noduri, lanțul de la nodul 66 la nodul 88 are lungimea 55, 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 T=2T=2.

Log in or sign up to be able to send submissions!