Pagini recente » Diferente pentru problema/bibel intre reviziile 4 si 3 | Diferente pentru algoritmiada-2018/runda-finala/regulament intre reviziile 1 si 2 | Atasamentele paginii Profil lamez0r | Diferente pentru problema/ktown intre reviziile 2 si 4 | Diferente pentru problema/aiacupalindroame intre reviziile 5 si 7
Nu exista diferente intre titluri.
Diferente intre continut:
h2. Cerinţă
Se dau $Q$ întrebări de forma $x y$ – unde $x$ şi $y$ sunt două noduri din arbore. Se cere să se răspundă pentru fiecare intrebare dacă $(x, y)$ este LCA palindrom sau nu. Spunem că $(x, y)$ e LCA palindrom dacă:
Se dau $Q$ întrebări de forma $x y$ – unde $x$ şi $y$ sunt două noduri din arbore. Se cere să se răspundă pentru fiecare intrebare dacă $(x, y)$ este **LCA-palindrom** sau nu. Spunem că $(x, y)$ e **LCA-palindrom** dacă:
# Drumul de la $x$ la $LCA (x, y)$ şi drumul de la $y$ la $LCA (x, y)$ au aceeasi lungime.
# Şirul de caractere corespunzător lanţului de la $x$ la $y$, care trece prin $LCA (x, y)$ să fie palindrom.
* $1 ≤ N ≤ 100.000$
* $1 ≤ Q ≤ 500.000$
* Pentru teste în valoare de $25$ de puncte $N ≤ 1.000$ şi $Q ≤ 5.000$
* Pentru teste în valoare de $65$ de puncte $N ≤ 20.000$ şi $Q ≤ 100.000$
* Pentru teste în valoare de $60$ de puncte $N ≤ 20.000$ şi $Q ≤ 100.000$
* Se garanteaza ca pentru fiecare query nodurile sunt distincte.
* Problema va fi evaluată pe teste în valoare de $90$ de puncte
* Se vor acorda $10$ puncte din oficiu
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
