#1185281 (C++23(gcc16)) No.3650 Teleportation Cycles

• 問題: No.3650 Teleportation Cycles
• ユーザー: itoito1234
• 提出日時: 2026-09-09 21:05:39
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 67 ms / 2,000 ms
• コード長: 5,385 bytes
• コンパイル時間: 6,552 ms
• コンパイル使用メモリ: 396,832 KB
• 実行使用メモリ: 73,272 KB
• 最終ジャッジ日時: 2026-09-09 21:05:49
• 合計ジャッジ時間: 8,155 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 36

ソースコード

#include <bits/stdc++.h>
using namespace std;

#include <atcoder/all>
using namespace atcoder;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define YES cout << "Yes" << endl;
#define NO cout << "No" << endl;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
// using mint = modint998244353;

class FunctionalGraph {
public:
    int n;
    std::vector<int> to;

    // 構造分解データ
    std::vector<int> cycle_id;        // 到達するサイクルのID
    std::vector<int> cycle_len;       // 到達するサイクルの長さ
    std::vector<int> cycle_entry;     // 到達するサイクル上の最初の頂点
    std::vector<int> cycle_pos;       // サイクル内でのインデックス
    std::vector<int> dist_to_cycle;   // サイクルまでの距離
    std::vector<bool> is_in_cycle;    // サイクル上の頂点か否か
    std::vector<std::vector<int>> cycles; // 各サイクルの構成頂点リスト

private:
    int max_log;
    std::vector<std::vector<int>> doubling; // 木部分移動用のダブリングテーブル

public:
    explicit FunctionalGraph(int n) 
        : n(n), to(n, -1), cycle_id(n, -1), cycle_len(n, 0),
          cycle_entry(n, -1), cycle_pos(n, -1), dist_to_cycle(n, 0),
          is_in_cycle(n, false) {}

    // 有向辺 u -> v を追加
    void add_edge(int u, int v) {
        to[u] = v;
    }

    // グラフ構築 (max_k: 想定される最大ステップ数)
    void build(long long max_k = 1e18) {
        // 1. 入次数管理（トポロジカルソート）で木部分とサイクル部分を分離
        std::vector<int> in_degree(n, 0);
        for (int i = 0; i < n; ++i) in_degree[to[i]]++;

        std::queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (in_degree[i] == 0) q.push(i);
        }

        std::vector<bool> is_tree(n, false);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            is_tree[u] = true;
            if (--in_degree[to[u]] == 0) q.push(to[u]);
        }

        // 2. サイクルの抽出
        int num_cycles = 0;
        for (int i = 0; i < n; ++i) {
            if (!is_tree[i] && cycle_id[i] == -1) {
                std::vector<int> cycle_nodes;
                int curr = i;
                while (cycle_id[curr] == -1) {
                    cycle_id[curr] = num_cycles;
                    is_in_cycle[curr] = true;
                    cycle_pos[curr] = cycle_nodes.size();
                    cycle_entry[curr] = curr;
                    cycle_nodes.push_back(curr);
                    curr = to[curr];
                }
                int sz = cycle_nodes.size();
                for (int v : cycle_nodes) cycle_len[v] = sz;
                cycles.push_back(cycle_nodes);
                num_cycles++;
            }
        }

        cout<<num_cycles;

        // 3. 逆向きBFSで木部分にサイクル情報を伝播
        std::vector<std::vector<int>> rev(n);
        std::queue<int> bq;
        for (int i = 0; i < n; ++i) {
            if (is_in_cycle[i]) {
                bq.push(i);
            } else {
                rev[to[i]].push_back(i);
            }
        }

        while (!bq.empty()) {
            int u = bq.front();
            bq.pop();
            for (int v : rev[u]) {
                dist_to_cycle[v] = dist_to_cycle[u] + 1;
                cycle_entry[v] = cycle_entry[u];
                cycle_id[v] = cycle_id[u];
                cycle_len[v] = cycle_len[u];
                bq.push(v);
            }
        }

        // 4. ダブリングテーブル構築
        max_log = 1;
        while ((1LL << max_log) <= max_k) max_log++;
        doubling.assign(max_log, std::vector<int>(n));

        for (int i = 0; i < n; ++i) doubling[0][i] = to[i];
        for (int k = 0; k < max_log - 1; ++k) {
            for (int i = 0; i < n; ++i) {
                doubling[k + 1][i] = doubling[k][doubling[k][i]];
            }
        }
    }

    // 頂点 v から k ステップ進んだ頂点を取得
    int jump(int v, long long k) const {
        if (k >= dist_to_cycle[v]) {
            // サイクル進入後: O(1) の余り計算
            long long rem = k - dist_to_cycle[v];
            int entry = cycle_entry[v];
            int cid = cycle_id[entry];
            int c_len = cycle_len[entry];
            int final_pos = (cycle_pos[entry] + rem) % c_len;
            return cycles[cid][final_pos];
        } else {
            // 木内部の移動: O(log K) のダブリング移動
            for (int i = 0; i < max_log; ++i) {
                if ((k >> i) & 1) v = doubling[i][v];
            }
            return v;
        }
    }

    // 頂点 u から到達可能な頂点の個数を取得 O(1)
    long long count_reachable(int u) const {
        return (long long)dist_to_cycle[u] + cycle_len[u];
    }
};

void solve() {
    // ここに1テストケース分の処理を書く
    int n;
    cin>>n;
    FunctionalGraph f(n);
    rep(i,n){
        int u;
        cin>>u;
        f.add_edge(i,u-1);
    }
    f.build();
}

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t = 1;
    // cin >> t; // テストケース数が最初に入力される問題の場合は、ここのコメントアウトを解除する
    
    while (t--) {
        solve();
    }
}