Alfabetik Qraf#12258

Alfabetik Qraf (Həll təhlili)

Problem Müəllifi:	turneja
Hazırlayan:	turneja
Redaktə edən:	turneja

Həll

İlk öncə, qrafın bir neçə bağlı komponentdən ibarət olacağını, hər birinin kök üzərində dövr və dövr olmayan zirvələrin dövrə doğru yönəldiyini qeyd edin.

DFS ilə dövrü və dövr olmayan zirvələri tapırıq və hər bir dövr olmayan zirvə üçün dövrə olan məsafəni və ona çatmaq üçün ilk dövr zirvəsini hesablayırıq.

$f (u, k)$ f(u, k) ilə $u$ -dan başlayaraq cari zirvənin çıxan kənarını $k$ dəfə izlədiyimiz zirvəni ifadə edək. Bu funksiyanın dəyərini $O (lo g n)$ \mathcal{O}(\log n) vaxtda qrafın ikili qaldırma cədvəlini quraraq tez bir zamanda hesablaya bilərik.

Sonra $v$ -nin $u$ -dan əlçatanlığını aşağıdakı kimi yoxlayırıq:

1. Əgər iki düyün $u$ və $v$ fərqli komponentlərə aiddirsə, cavab $- 1$ -dir.

2. Əgər $u$ dövr zirvəsidirsə və $v$ dövr olmayan zirvəsidirsə, cavab $- 1$ -dir.

3. Əgər $u$ və $v$ dövr olmayan zirvələrdirsə, onda $d i s t_{u}$ dist_u və $d i s t_{v}$ dist_v-ni $u$ və $v$ -nin dövrə olan məsafələri kimi təyin edək. Onda əgər $d i s t_{u} < d i s t_{v}$ dist_u < dist_v və ya $f (u, d i s t_{u} - d i s t_{v}) \neq = v$ f(u, dist_u - dist_v) \neq v-dirsə, cavab $- 1$ -dir, əks halda $v$ $u$ -dan əlçatandır və məsafə $d i s t_{u} - d i s t_{v}$ dist_u - dist_v-dir.

4. Əgər $v$ dövr zirvəsidirsə, onda $v$ $u$ -dan əlçatandır və məsafəni aşağıdakı kimi hesablaya bilərik: $u$ dövr zirvəsi olduğunu qəbul edək. Sonra dövrü uzunluğu $L$ olan dövrvi massiv kimi qəbul edin və məsafəni $(p o s_{v} - p o s_{u} + L) mod L$ (pos_v - pos_u + L) \mod L olaraq hesablayın. Əgər $u$ dövr üzərində deyilsə, onda $w$ -ni $u$ -dan çatmaq üçün ilk dövr zirvəsi kimi təyin edək və məsafəni $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 olaraq hesablayın.

Cavab $- 1$ -dirsə, əvvəlcə $u$ -dan $v$ -yə olan məsafəni $d$ olaraq təyin edin. $k$ -ci hərfi səmərəli şəkildə hesablamaq üçün ikili qaldırma cədvəlini əlavə məlumatlarla genişləndiririk. Hər bir zirvə $u$ və güc $2^{j}$ 2^j üçün $d a t a [u] [j]$ data[u][j] blokunu əvvəlcədən hesablayırıq ki, bu da $u$ -dan başlayaraq növbəti $2^{j}$ 2^j kənarını keçməyin təsirini xülasə edir. Hər bir blok aşağıdakıları saxlayır:

$u p$ : son nöqtə $f (u, 2^{j})$ f(u,2^j).

$p r e f$ : bu seqmentdəki ilk hərf.

$s u f$ : bu seqmentdəki son hərf.

$p r e f c t$ prefct: $p r e f$ -nin ilkin ardıcıllığının uzunluğu (kənarlarla).

$s u f c t$ : $s u f$ -nin son ardıcıllığının uzunluğu (kənarlarla).

$l e n$ : seqmentdəki kənarların sayı (bərabər $2^{j}$ 2^j).

$e n t i r e$ : seqmentdəki bütün kənarların eyni hərfi daşıyıb-daşımadığını bildirir.

$sz$ : yalnız bu seqment tərəfindən istehsal olunan ümumi uzunluq $∣ S ∣$ (böyük bir sentinel $+ \infty$ ilə məhdudlaşdırılır).

Eyni hərflə ardıcıl $t$ kənarının bir ardıcıllığı $S$ -yə $2^{t} - 1$ 2^t - 1 simvol əlavə edir. Yeterince böyük $t$ dəyərləri üçün (məsələn, $t = 50$ t=50 çünki $2^{50} - 1 > 1 0^{12}$ 2^{50}-1>10^{12}) $+ \infty$ -yə məhdudlaşdırmağa diqqət edin ki, aşırı yüklənməsin.

Bu quruluş, iki blok üçün $O (1)$ vaxtda işləyən bir birləşdirmə funksiyası yazmağımıza imkan verir.

$k$ -ci simvolu çıxarmaq üçün, $u$ -dan başlayaraq $k$ -ni istehsal edən ölçünü sərt şəkildə aşağıda saxlayaraq mümkün olan ən böyük bloku alırıq və keçilən kənarların sayını $d$ -dən aşağıda saxlayırıq.

Bundan sonra, $u$ -dan başlayan növbəti tək kənarı nəzərə alın. Əgər $m er g e (c u r, d a t a [u] [0]) . sz \geq k$ merge(cur, data[u][0]).sz \geq k-dirsə, onda $k$ -ci simvol həmin kənardakı hərfdir, əks halda bütün $d$ kənarlarını istehlak etsə belə $∣ S ∣ < k$ |S|<k olur və cavab $- 1$ -dir.

Vaxt mürəkkəbliyi: $O ((n + q) lo g n)$ \mathcal{O}((n + q) \log n)

Yaddaş mürəkkəbliyi: $O (n lo g n)$ \mathcal{O}(n \log n)

Birləşdirmə funksiyasının detalları tətbiqdə qaldırılır.

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