CSES 1160：Planets Queries II

CSES 1160：Planets Queries II

題目大意：有 $n$ 個星球，每個星球可以傳送到編號為 $t_i$ 的星球，給你星球編號 $a$ 和 $b$，請你回答 $a$ 星球能不能到達 $b$ 星球，如果可以，輸出最少的傳送距離。

解法：先看是在環裡或是在邊上，可以記錄最後會通到的環編號，還有邊上的高度，最後再用倍增法。

$\text{Code：}$

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 200005;
const int H = __lg (SIZE) + 1;

int to[H + 1][SIZE], cg[SIZE], csiz[SIZE], h[SIZE], pos[SIZE];
bool vs[SIZE], cs[SIZE];

int fd (int pos, int k) {
    if (k == 0)
        return pos;
    return fd (to[__lg (k & -k)][pos], k - (k & -k));
}

void solve() {
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++)
        cin >> to[0][i];

    int cl = 0, cz;
    for (int i = 1; i <= n; i++) {
        if (vs[i])
            continue;
        stack<int> st;
        int now = i;
        while (1) {
            vs[now] = 1;
            st.push (now);
            now = to[0][now];
            if (cs[now]) {
                int l = 0;
                while (st.size()) {
                    h[st.top()] = ++l;
                    cg[st.top()] = cg[now];
                    st.pop();
                }
                break;
            }
            if (h[now]) {
                int l = h[now];
                while (st.size()) {
                    h[st.top()] = ++l;
                    cg[st.top()] = cg[now];
                    st.pop();
                }
                break;
            }
            if (vs[now] && h[now] == 0) {
                stack<int> cyc;
                while (1) {
                    cyc.push (st.top());
                    st.pop();
                    if (cyc.top() == now)
                        break;
                }
                ++cl, cz = cyc.size();
                int p = 0;
                while (cyc.size()) {
                    cg[cyc.top()] = cl;
                    csiz[cyc.top()] = cz;
                    cs[cyc.top()] = 1;
                    pos[cyc.top()] = p++;
                    cyc.pop();
                }
                int l = 0;
                while (st.size()) {
                    h[st.top()] = ++l;
                    cg[st.top()] = cg[now];
                    st.pop();
                }
                break;
            }
        }
    }

    for (int i = 1; i <= H; i++)
        for (int j = 1; j <= n; j++)
            to[i][j] = to[i - 1][to[i - 1][j]];

    while (q--) {
        int a, b;
        cin >> a >> b;
        if (h[a] < h[b]) {
            cout << "-1\n";
            continue;
        }
        if (cg[a] != cg[b]) {
            cout << "-1\n";
            continue;
        }
        int ans = h[a] - h[b];
        a = fd (a, h[a] - h[b]);
        if (h[b]) {
            if (a != b)
                cout << "-1\n";
            else
                cout << ans << '\n';
            continue;
        }
        cout << ans + (pos[b] + csiz[b] - pos[a]) % csiz[b] << '\n';
    }
}

int main() {
    ios::sync_with_stdio (false), cin.tie (0);
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！