Solutia problemei Tubeyou
In primul rand, putem aduna la fiecare durata[i] numarul K, si de acum putem sa consideram K = 0.
Pentru 10 puncte
Vom mentine sirul next[i] si vom face operatiile in ordinea data. La update, putem parcurge tot sirul next[] si daca next[i] == x, il schimbam in next[x]. La query, putem merge din a in next[a] pana cand am mai ajuns intr-un nod vizitat la acest query si vom retine care este timpul timpA la care vom deschide fiecare videoclip vizitat. Apoi din b vom face o parcurgere asemanatoare. La final, se considera videoclipurile vizitate atat din a, cat si din b, si se ia acela pentru care max(timpA, timpB) este cat mai mic. Daca nu exista nod vizitat de ambii, afisam infinit.
Pentru 100 de puncte
Mai intai remarcam ca structura grafului format din muchiile orientate (i, next[i]) este o multime de componente conexe, iar fiecare componenta conexa este un ciclu simplu de care sunt agatati mai multi arbori. Ca observatie, ciclcul poate fi format si dintr-un singur nod, in caz ca next[x] == x.
La un query ce ar trebui sa vedem este in primul rand daca nodurile se afla in aceeasi componenta conexa. In caz ca nu, afisam infinit. Altfel, ar trebui sa stim daca fac parte din acelasi arbore cu radacina pe ciclul componentei lor, sau se afla in arbori diferiti. Daca se afla in acelasi arbore, afisam maximul intre distanta de la a la lca(a, b) si distanta de la b la lca(a, b) (prin lca am notat lowest common ancestor). Daca se afla pe arbori diferiti, notam cu A radacina arborelui lui a si cu B radacina arborelui lui b. Atunci raspunsul este minim(maxim(dist(a, A) + dist(A, B), dist(b, B)), maxim(dist(b, B) + dist(B, A), dist(a, A))).
La un update e ca si cand am modifica durata[x] = 0, mai putin pentru clipele in care se da un query in care a sau b este egal cu x, caz in care reconsideram durata[x] la valoarea ei normala. Vom face distinctie intre cazul in care nodul apartine unui ciclu sau strict unui arbore.
Prin urmare avem de efectuat operatii de genul:
- Scade valoarea unui nod intr-un arbore
- Scade valoarea unui nod intr-un ciclu
- Afla distanta de la un nod la un stramos al sau intr-un arbore
- Afla distanta de la un nod la altul intr-un ciclu
Aceste operatii ne duc cu gandul la liniarizarea plus-minus a arborilor si la mentinerea unui arbore indexat binar atat peste aceste liniarizari, cat si peste ciclii. Putem mentine un singur aib pentru toti arborii, daca le concatenam liniarizarile. Asemanator putem proceda cu ciclii. Mentionam ca mai trebuie sa obtinem si lca in timp logaritmic.
Complexitate finala: timp O((N + Q) * logN), memorie O(N * logN) (pentru precalcularea necesara pentru lca).
