Graphe Alphabétique#12258

Graphe Alphabétique (Corrigé)

Auteur du problème :	turneja
Préparé par :	turneja
Édité par :	turneja

Solution

Tout d'abord, remarquez que le graphe sera constitué de plusieurs composants connectés, chacun d'eux étant un arbre dirigé avec un cycle à la racine et les sommets non-cycliques pointant vers le cycle.

Avec DFS, nous trouvons le cycle et les sommets non-cycliques et pour chaque sommet non-cyclique, nous calculons la distance au cycle et le premier sommet du cycle accessible depuis celui-ci.

Désignons par $f (u, k)$ f(u, k) le sommet que nous atteignons en partant de $u$ et en suivant l'arête sortante du sommet actuel $k$ fois. La valeur de cette fonction peut être calculée rapidement en $O (lo g n)$ \mathcal{O}(\log n) en construisant une table de levée binaire du graphe.

Ensuite, nous testons l'accessibilité de $v$ depuis $u$ de la manière suivante :

1. Si deux nœuds $u$ et $v$ appartiennent à des composants différents, alors la réponse est $- 1$ .

2. Si $u$ est un sommet de cycle et $v$ est un sommet non-cyclique, alors la réponse est $- 1$ .

3. Si $u$ et $v$ sont des sommets non-cycliques, alors désignons par $d i s t_{u}$ dist_u et $d i s t_{v}$ dist_v les distances de $u$ et $v$ au cycle, respectivement. Alors si $d i s t_{u} < d i s t_{v}$ dist_u < dist_v ou $f (u, d i s t_{u} - d i s t_{v}) \neq = v$ f(u, dist_u - dist_v) \neq v, la réponse est $- 1$ , sinon $v$ est accessible depuis $u$ et la distance est $d i s t_{u} - d i s t_{v}$ dist_u - dist_v.

4. Si $v$ est un sommet de cycle, alors $v$ sera accessible depuis $u$ , et la distance peut être calculée de la manière suivante : supposons que $u$ est un sommet de cycle. Ensuite, traitez le cycle comme un tableau circulaire de longueur $L$ et calculez la distance comme $(p o s_{v} - p o s_{u} + L) mod L$ (pos_v - pos_u + L) \mod L. Si $u$ n'est pas sur le cycle, alors nous désignons $w$ comme le premier sommet de cycle accessible depuis $u$ et calculons la distance comme $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 réponse n'est pas $- 1$ , désignons d'abord la distance de $u$ à $v$ comme $d$ . Pour calculer la $k$ -ème lettre efficacement, nous augmentons la table de levée binaire avec des informations supplémentaires. Pour chaque sommet $u$ et puissance $2^{j}$ 2^j, nous pré-calculons un bloc $d a t a [u] [j]$ data[u][j] qui résume l'effet de traverser les $2^{j}$ 2^j arêtes suivantes à partir de $u$ . Chaque bloc stocke :

$u p$ : le point d'arrivée $f (u, 2^{j})$ f(u,2^j).

$p r e f$ : la première lettre sur ce segment.

$s u f$ : la dernière lettre sur ce segment.

$p r e f c t$ prefct : longueur (en arêtes) de la course initiale de $p r e f$ .

$s u f c t$ : longueur (en arêtes) de la course finale de $s u f$ .

$l e n$ : nombre d'arêtes dans le segment (égal à $2^{j}$ 2^j).

$e n t i r e$ : si toutes les arêtes dans le segment portent la même lettre.

$sz$ : longueur totale $∣ S ∣$ produite par ce segment seul (limitée à un grand sentinelle $+ \infty$ ).

Remarquez qu'une course de $t$ arêtes consécutives avec la même lettre contribue $2^{t} - 1$ 2^t - 1 caractères à $S$ . Faites attention à pour des valeurs suffisamment grandes de $t$ (par exemple, $t = 50$ t=50 puisque $2^{50} - 1 > 1 0^{12}$ 2^{50}-1>10^{12}) limiter à $+ \infty$ pour éviter un dépassement.

Cette configuration nous permet d'écrire une fonction de fusion pour deux blocs qui fonctionne en $O (1)$ .

Pour extraire le $k$ -ème caractère, nous prenons de manière gourmande le plus grand bloc possible à partir de $u$ tout en gardant la taille produite strictement inférieure à $k$ et la quantité d'arêtes traversées strictement inférieure à $d$ .

Ensuite, après cela, considérez la prochaine arête unique partant de $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, alors le $k$ -ème caractère est égal à la lettre sur cette arête, sinon même en consommant toutes les arêtes $d$ donne $∣ S ∣ < k$ |S|<k et la réponse est $- 1$ .

Complexité temporelle : $O ((n + q) lo g n)$ \mathcal{O}((n + q) \log n)

Complexité mémoire : $O (n lo g n)$ \mathcal{O}(n \log n)

Les détails de la fonction de fusion sont laissés dans l'implémentation.

#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++