Grafo Alfabético#12258

Grafo Alfabético (Editorial)

Autor del Problema:	turneja
Preparado por:	turneja
Editado por:	turneja

Solución

Primero, observa que el grafo consistirá en múltiples componentes conectados, cada uno de los cuales será un árbol dirigido con un ciclo en la raíz y los vértices no cíclicos apuntando hacia el ciclo.

Con DFS, encontramos el ciclo y los vértices no cíclicos y para cada vértice no cíclico calculamos la distancia al ciclo y el primer vértice del ciclo alcanzable desde él.

Denotemos por $f (u, k)$ f(u, k) el vértice que alcanzamos comenzando desde $u$ y siguiendo la arista saliente del vértice actual $k$ veces. El valor de esta función se puede calcular rápidamente en $O (lo g n)$ \mathcal{O}(\log n) construyendo una tabla de levantamiento binario del grafo.

Luego probamos la alcanzabilidad de $v$ desde $u$ de la siguiente manera:

1. Si dos nodos $u$ y $v$ pertenecen a diferentes componentes, entonces la respuesta es $- 1$ .

2. Si $u$ es un vértice cíclico y $v$ es un vértice no cíclico, entonces la respuesta es $- 1$ .

3. Si $u$ y $v$ son vértices no cíclicos, entonces denotemos por $d i s t_{u}$ dist_u y $d i s t_{v}$ dist_v las distancias desde $u$ y $v$ al ciclo, respectivamente. Entonces, si $d i s t_{u} < d i s t_{v}$ dist_u < dist_v o $f (u, d i s t_{u} - d i s t_{v}) \neq = v$ f(u, dist_u - dist_v) \neq v, la respuesta es $- 1$ , de lo contrario, $v$ es alcanzable desde $u$ y la distancia es $d i s t_{u} - d i s t_{v}$ dist_u - dist_v.

4. Si $v$ es un vértice cíclico, entonces $v$ será alcanzable desde $u$ , y la distancia se puede calcular de la siguiente manera: supongamos que $u$ es un vértice cíclico. Entonces trata el ciclo como un arreglo circular de longitud $L$ y calcula la distancia como $(p o s_{v} - p o s_{u} + L) mod L$ (pos_v - pos_u + L) \mod L. Si $u$ no está en el ciclo, entonces denotamos $w$ como el primer vértice cíclico alcanzable desde $u$ y calculamos la distancia como $d i s t_{u} + (p o s_{v} - p o s_{w} + L) mod L$ dist_u +(pos_v - pos_w + L) \mod L.

Si la respuesta no es $- 1$ , primero denotamos la distancia desde $u$ hasta $v$ como $d$ . Para calcular la $k$ -ésima letra de manera eficiente, aumentamos la tabla de levantamiento binario con información adicional. Para cada vértice $u$ y potencia $2^{j}$ 2^j, precomputamos un bloque $d a t a [u] [j]$ data[u][j] que resume el efecto de recorrer las siguientes $2^{j}$ 2^j aristas comenzando desde $u$ . Cada bloque almacena:

$u p$ : el punto final $f (u, 2^{j})$ f(u,2^j).

$p r e f$ : la primera letra en este segmento.

$s u f$ : la última letra en este segmento.

$p r e f c t$ prefct: longitud (en aristas) de la ejecución inicial de $p r e f$ .

$s u f c t$ : longitud (en aristas) de la ejecución final de $s u f$ .

$l e n$ : número de aristas en el segmento (igual a $2^{j}$ 2^j).

$e n t i r e$ : si todas las aristas en el segmento llevan la misma letra.

$sz$ : longitud total $∣ S ∣$ producida por este segmento solo (limitada a un gran centinela $+ \infty$ ).

Observa que una ejecución de $t$ aristas consecutivas con la misma letra contribuye con $2^{t} - 1$ 2^t - 1 caracteres a $S$ . Ten cuidado de para valores suficientemente grandes de $t$ (por ejemplo, $t = 50$ t=50 ya que $2^{50} - 1 > 1 0^{12}$ 2^{50}-1>10^{12}) limitar a $+ \infty$ para evitar desbordamientos.

Esta configuración nos permite escribir una función de combinación para dos bloques que funciona en $O (1)$ .

Para extraer el carácter $k$ -ésimo, tomamos de manera codiciosa el bloque más grande posible comenzando desde $u$ mientras mantenemos el tamaño producido estrictamente por debajo de $k$ y la cantidad de aristas recorridas estrictamente por debajo de $d$ .

Luego, después de esto, considera la siguiente arista única comenzando en $u$ . Si $m er g e (c u r, d a t a [u] [0]) . sz \geq k$ merge(cur, data[u][0]).sz \geq k entonces el carácter $k$ -ésimo es igual a la letra en esa arista, de lo contrario, incluso consumiendo todas las $d$ aristas da como resultado $∣ S ∣ < k$ |S|<k y la respuesta es $- 1$ .

Complejidad de tiempo: $O ((n + q) lo g n)$ \mathcal{O}((n + q) \log n)

Complejidad de memoria: $O (n lo g n)$ \mathcal{O}(n \log n)

Los detalles de la función de combinación se dejan en la implementación.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pb_ds;

#define endl "\n"
#define ll long long
#define IOS ios_base::sync_with_stdio(false); cin.tie(nullptr);

const int N = 2e5 + 5;
const int K = 19;
const ll INF = 1e18;

int up[K][N];
int color[N];
int group[N];
bool cycle[N];
int pos[N];
int entry[N];
int sz[N];
int dist[N];
int parent[N];
char wt[N];
ll pw[50];

void dfs(int u, int p) {

    color[u] = 1;
    parent[u] = p;
    int v = up[0][u];
    if (color[v] == 0) {
        dfs(v, u);
    } else if (color[v] == 1) {
        int x = u;
        vector<int> cyc;
        while (x != v) {
            cyc.push_back(x);
            x = parent[x];
        }
        cyc.push_back(v);
        reverse(cyc.begin(), cyc.end());
        for (int i = 0; i < (int)cyc.size(); i++) {
            int x = cyc[i];
            cycle[x] = true;
            pos[x] = i;
            dist[x] = 0;
            sz[x] = cyc.size();
            group[x] = v;
        }
    }
    color[u] = 2;
    if (!cycle[u]) {
        group[u] = group[v];
        if (cycle[v]) {
            dist[u] = 1;
            entry[u] = v;
        } else {
            dist[u] = dist[v] + 1;
            entry[u] = entry[v];
        }
    }
}

struct Data {
    char pref;
    char suf;
    int prefct;
    int sufct;
    int len;
    bool entire;
    ll sz;

    Data () {}

    Data(char c) {
        pref = c;
        suf = c;
        prefct = 1;
        sufct = 1;
        len = 1;
        entire = true;
        sz = 1;
    }
};

Data combine(Data left, Data right) {
    Data cur;
    cur.pref = left.pref;
    cur.suf = right.suf;
    if (left.entire && left.pref == right.pref) {
        cur.prefct = left.len + right.prefct;
    } else {
        cur.prefct = left.prefct;
    }
    if (right.entire && left.suf == right.pref) {
        cur.sufct = left.sufct + right.len;
    } else {
        cur.sufct = right.sufct;
    }

    cur.len = left.len + right.len;
    cur.entire = left.entire && right.entire && left.pref == right.pref;
    if (left.sz >= INF || right.sz >= INF) {
        cur.sz = INF;
    } else {
        cur.sz = left.sz + right.sz;
        if (left.suf == right.pref) {
            cur.sz -= pw[left.sufct];
            cur.sz -= pw[right.prefct];
            cur.sz += (left.sufct + right.prefct >= 50 ? INF : pw[left.sufct + right.prefct]);
        }
        cur.sz = min(cur.sz, INF);
    }
    return cur;
}

Data dat[K][N];

int kth(int u, int k) {
    for (int i = K - 1; i >= 0; i--) {
        int c = k & (1 << i);
        if (c) {
            u = up[i][u];
        }
    }
    return u;
}

int main() {
    IOS;
    pw[0] = 0;
    for (int i = 1; i < 50; i++) {
        pw[i] = ((pw[i - 1] + 1) * 2) - 1;
        pw[i] = min(pw[i], INF);
    }
    int n, q;
    cin >> n >> q;
    for (int i = 0; i < n; i++) {
        int j; char c;
        cin >> j >> c;
        j--;
        up[0][i] = j;
        dat[0][i] = Data(c);
        wt[i] = c;
    }
    for (int k = 1; k < K; k++) {
        for (int i = 0; i < n; i++) {
            up[k][i] = up[k - 1][up[k - 1][i]];
            dat[k][i] = combine(dat[k - 1][i], dat[k - 1][up[k - 1][i]]);
        }
    }
    for (int i = 0; i < n; i++) {
        if (color[i] == 0) {
            dfs(i, i);
        }
    }
    for (int i = 0; i < q; i++) {
        int u, v; ll k;
        cin >> u >> v >> k;
        u--, v--;
        if (group[u] != group[v] || (cycle[u] && !cycle[v]) || u == v) {
            cout << -1 << endl;
            continue;
        }
        int d = 0;
        if (!cycle[u] && !cycle[v]) {
            int k = dist[u] - dist[v];
            if (k < 0) {
                cout << -1 << endl;
                continue;
            }
            int vc = kth(u, k);
            if (vc != v) {
                cout << -1 << endl;
                continue;
            }
            d = k;
        } else {
            int U = u;
            if (!cycle[u]) {
                d += dist[u];
                U = entry[u];
            }
            if (pos[U] <= pos[v]) {
                d += pos[v] - pos[U];
            } else {
                d += sz[U] - pos[U] + pos[v];
            }
        }
        if (k == 1) {
            cout << wt[u] << endl;
            continue;
        }
        if (d == 1) {
            cout << -1 << endl;
            continue;
        }
        Data cur = dat[0][u];
        u = up[0][u];
        for (int j = K - 1; j >= 0; j--) {
            Data nx = combine(cur, dat[j][u]);
            if (nx.sz < k && nx.len < d) {
                cur = nx;
                u = up[j][u];
            }
        }
        Data tmp = Data(wt[u]);
        cur = combine(cur, tmp);
        if (cur.sz < k) {
            cout << -1 << endl;
        } else {
            cout << wt[u] << endl;
        }
    }
    return 0;
}

C++