Alphabetic Graph#12258

Alphabetic Graph (Editorial)

Problem Author:	turneja
Prepared by:	turneja
Edited by:	turneja

Solution

First, notice that the graph will consist of multiple connected components, each of which will be a directed tree with a cycle on the root and the non-cycle vertices pointing towards the cycle.

With DFS, we find the cycle and non-cycle vertices and for each non-cycle vertex we calculate the distance to the cycle and the first cycle vertex reachable from it.

Denote by $f (u, k)$ f(u, k) the vertex we reach by starting from $u$ and following the outgoing edge of the current vertex $k$ times. The value of this function can be calculated quickly in $O (lo g n)$ \mathcal{O}(\log n) by building a binary lifting table of the graph.

Then we test reachability of $v$ from $u$ in the following way:

1. If two nodes $u$ and $v$ belong to different components then the answer is $- 1$ .

2. If $u$ is a cycle vertex and $v$ is a non-cycle vertex then the answer is $- 1$ .

3. If $u$ and $v$ are non-cycle vertices, then denote by $d i s t_{u}$ dist_u and $d i s t_{v}$ dist_v the distances from $u$ and $v$ to the cycle, respectively. Then if $d i s t_{u} < d i s t_{v}$ dist_u < dist_v or $f (u, d i s t_{u} - d i s t_{v}) \neq = v$ f(u, dist_u - dist_v) \neq v the answer is $- 1$ , otherwise $v$ is reachable from $u$ and the distance is $d i s t_{u} - d i s t_{v}$ dist_u - dist_v.

4. If $v$ is a cycle vertex then $v$ will be reachable from $u$ , and the distance can be calculated in the following way: assume $u$ is a cycle vertex. Then treat the cycle as a circular array with length $L$ and calculate the distance as $(p o s_{v} - p o s_{u} + L) mod L$ (pos_v - pos_u + L) \mod L. If $u$ is not on the cycle then we denote $w$ as the first cycle vertex reachable from $u$ and calculate the distance as $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.

If the answer is not $- 1$ , first denote the distance from $u$ to $v$ as $d$ . To calculate the $k$ -th letter efficiently we augment the binary lifting table with additional information. For every vertex $u$ and power $2^{j}$ 2^j we precompute a block $d a t a [u] [j]$ data[u][j] that summarizes the effect of traversing the next $2^{j}$ 2^j edges starting from $u$ . Each block stores:

$u p$ : the endpoint $f (u, 2^{j})$ f(u,2^j).

$p r e f$ : the first letter on this segment.

$s u f$ : the last letter on this segment.

$p r e f c t$ prefct: length (in edges) of the initial run of $p r e f$ .

$s u f c t$ : length (in edges) of the final run of $s u f$ .

$l e n$ : number of edges in the segment (equals $2^{j}$ 2^j).

$e n t i r e$ : whether all edges in the segment carry the same letter.

$sz$ : total length $∣ S ∣$ produced by this segment alone (capped at a large sentinel $+ \infty$ ).

Notice that a run of $t$ consecutive edges with the same letter contributes $2^{t} - 1$ 2^t - 1 characters to $S$ . Take care to for sufficiently large values of $t$ (e.g. $t = 50$ t=50 since $2^{50} - 1 > 1 0^{12}$ 2^{50}-1>10^{12}) clamp to $+ \infty$ to avoid overflow.

This setup allows us to write a merge function for two blocks that works in $O (1)$ .

To extract the $k$ -th character, we greedily take the largest possible block starting from $u$ while keeping the produced size strictly below $k$ and the amount of edges traversed strictly below $d$ .

Then after this, consider the next single edge starting at $u$ . If $m er g e (c u r, d a t a [u] [0]) . sz \geq k$ merge(cur, data[u][0]).sz \geq k then the $k$ -th character equals the letter on that edge, otherwise even consuming all $d$ edges yields $∣ S ∣ < k$ |S|<k and the answer is $- 1$ .

Time complexity: $O ((n + q) lo g n)$ \mathcal{O}((n + q) \log n)

Memory complexity: $O (n lo g n)$ \mathcal{O}(n \log n)

The details of the merge function are left in the implementation.

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