musuroi

Algoritmul, pas cu pas

Fiecare celulă are un singur succesor → un graf funcțional. Traiectoria de la $A$ este un drum unic care, într-un graf finit, intră inevitabil într-un ciclu (forma „rho": o coadă urmată de un ciclu).

Descompunere

Precalculăm, pentru fiecare celulă: distanța până la ciclu $\text{dist}$, ciclul în care intră (lungime $\lambda$) și poziția pe ciclu.

Răspunsul la o întrebare

• $B$ pe ciclul lui $A$: furnica intră pe ciclu și ajunge la $B$. Prima sosire: $d = \text{dist}(A) + \big(\text{pos}(B) - \text{pos}(\text{intrarea lui } A)\big) \bmod \lambda$ A $K$-a sosire: $d + (K-1)\lambda$.
• $B$ transient (în coadă): $B$ e vizitat cel mult o dată, deci doar $K=1$ are sens; răspunsul e distanța de la $A$ la $B$ ($= \text{dist}(A) - \text{dist}(B)$, dacă $B$ e chiar pe drum). Verificăm cu binary lifting că saltul cu $\text{dist}(A) - \text{dist}(B)$ pași din $A$ ajunge exact în $B$.
• $A = B$ și $K=1$: răspuns $0$.