Алфавітний Граф#12258

Алфавітний Граф (Розбір)

Автор проблеми:	turneja
Підготовлено:	turneja
Редаговано:	turneja

Рішення

По-перше, зверніть увагу, що граф складатиметься з кількох зв'язаних компонентів, кожна з яких буде спрямованим деревом з циклом на корені, а нециклічні вершини вказуватимуть на цикл.

За допомогою DFS ми знаходимо цикл і нециклічні вершини, і для кожної нециклічної вершини обчислюємо відстань до циклу та першу вершину циклу, до якої можна дістатися з неї.

Позначимо $f (u, k)$ f(u, k) як вершину, яку ми досягаємо, починаючи з $u$ і слідуючи за вихідною дугою поточної вершини $k$ разів. Значення цієї функції можна швидко обчислити за $O (lo g n)$ \mathcal{O}(\log n), побудувавши таблицю бінарного підйому графа.

Потім ми перевіряємо досяжність $v$ з $u$ наступним чином:

1. Якщо дві вершини $u$ і $v$ належать до різних компонентів, то відповідь - $- 1$ .

2. Якщо $u$ є вершиною циклу, а $v$ - нециклічною вершиною, то відповідь - $- 1$ .

3. Якщо $u$ і $v$ є нециклічними вершинами, то позначимо $d i s t_{u}$ dist_u і $d i s t_{v}$ dist_v відстані від $u$ і $v$ до циклу відповідно. Тоді, якщо $d i s t_{u} < d i s t_{v}$ dist_u < dist_v або $f (u, d i s t_{u} - d i s t_{v}) \neq = v$ f(u, dist_u - dist_v) \neq v, відповідь - $- 1$ , в іншому випадку $v$ досяжна з $u$ , а відстань дорівнює $d i s t_{u} - d i s t_{v}$ dist_u - dist_v.

4. Якщо $v$ є вершиною циклу, то $v$ буде досяжна з $u$ , і відстань можна обчислити наступним чином: припустимо, що $u$ є вершиною циклу. Тоді розглядаємо цикл як круговий масив довжини $L$ і обчислюємо відстань як $(p o s_{v} - p o s_{u} + L) mod L$ (pos_v - pos_u + L) \mod L. Якщо $u$ не знаходиться на циклі, то позначимо $w$ як першу вершину циклу, до якої можна дістатися з $u$ , і обчислюємо відстань як $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.

Якщо відповідь не $- 1$ , спочатку позначимо відстань від $u$ до $v$ як $d$ . Щоб ефективно обчислити $k$ -ий символ, ми доповнюємо таблицю бінарного підйому додатковою інформацією. Для кожної вершини $u$ і степеня $2^{j}$ 2^j ми попередньо обчислюємо блок $d a t a [u] [j]$ data[u][j], який узагальнює ефект проходження наступних $2^{j}$ 2^j дуз, починаючи з $u$ . Кожен блок зберігає:

$u p$ : кінцева точка $f (u, 2^{j})$ f(u,2^j).

$p r e f$ : перша літера на цьому сегменті.

$s u f$ : остання літера на цьому сегменті.

$p r e f c t$ prefct: довжина (в дугах) початкового пробігу $p r e f$ .

$s u f c t$ : довжина (в дугах) фінального пробігу $s u f$ .

$l e n$ : кількість дуз у сегменті (дорівнює $2^{j}$ 2^j).

$e n t i r e$ : чи всі дуги в сегменті несуть одну й ту ж літеру.

$sz$ : загальна довжина $∣ S ∣$ , що виробляється цим сегментом (обмежена великим значенням $+ \infty$ ).

Зверніть увагу, що пробіг з $t$ послідовних дуз з однією й тією ж літерою вносить $2^{t} - 1$ 2^t - 1 символів у $S$ . Будьте обережні, щоб для достатньо великих значень $t$ (наприклад, $t = 50$ t=50, оскільки $2^{50} - 1 > 1 0^{12}$ 2^{50}-1>10^{12}) обмежити до $+ \infty$ , щоб уникнути переповнення.

Ця налаштування дозволяє нам написати функцію злиття для двох блоків, яка працює за $O (1)$ .

Щоб витягти $k$ -ий символ, ми жадібно беремо найбільший можливий блок, починаючи з $u$ , при цьому зберігаючи вироблений розмір строго нижче $k$ і кількість дуз, що проходять, строго нижче $d$ .

Потім після цього розглядаємо наступну одиничну дугу, що починається з $u$ . Якщо $m er g e (c u r, d a t a [u] [0]) . sz \geq k$ merge(cur, data[u][0]).sz \geq k, то $k$ -ий символ дорівнює літері на цій дузі, в іншому випадку навіть споживши всі $d$ дуз, отримаємо $∣ S ∣ < k$ |S|<k і відповідь - $- 1$ .

Часова складність: $O ((n + q) lo g n)$ \mathcal{O}((n + q) \log n)

Пам'яттєва складність: $O (n lo g n)$ \mathcal{O}(n \log n)

Деталі функції злиття залишені в реалізації.

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

using namespace std;
using namespace __gnu_pbds;

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