#1180101 (C++23) No.3650 Teleportation Cycles

• 問題: No.3650 Teleportation Cycles
• ユーザー: ウソチー
• 提出日時: 2026-08-28 23:03:35
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 53 ms / 2,000 ms
• コード長: 12,703 bytes
• コンパイル時間: 5,162 ms
• コンパイル使用メモリ: 375,536 KB
• 実行使用メモリ: 39,508 KB
• 最終ジャッジ日時: 2026-08-28 23:03:48
• 合計ジャッジ時間: 7,809 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge2_1

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

ソースコード

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

#include <iostream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>

struct FastIO {
    FastIO() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
};
inline FastIO fast_io_init;

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
    return is >> p.first >> p.second;
}

template <typename Tuple, std::size_t... I>
void read_tuple_impl(std::istream& is, Tuple& t, std::index_sequence<I...>) {
    (..., (is >> std::get<I>(t)));
}

template <typename... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& t) {
    read_tuple_impl(is, t, std::index_sequence_for<Args...>{});
    return is;
}

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& elem : v) {
        is >> elem;
    }
    return is;
}

using default_type = long;

template <typename... Args>
void read(Args&... args) {
    (std::cin >> ... >> args);
}

template <typename T = default_type>
T read_val() {
    T val;
    std::cin >> val;
    return val;
}

template <typename T1 = default_type, typename T2 = default_type>
std::pair<T1, T2> read_pair() {
    std::pair<T1, T2> p;
    std::cin >> p;
    return p;
}

template <typename... Args>
std::tuple<Args...> read_tuple() {
    std::tuple<Args...> t;
    std::cin >> t;
    return t;
}

template <typename T = default_type>
std::vector<T> read_vec(int n) {
    std::vector<T> v(n);
    std::cin >> v;
    return v;
}

template <typename T = default_type>
std::vector<T> read_vec() {
    int n;
    std::cin >> n;
    return read_vec<T>(n);
}

template <typename T1 = default_type, typename T2 = default_type>
std::vector<std::pair<T1, T2>> read_vec_pair(int n) {
    std::vector<std::pair<T1, T2>> v(n);
    std::cin >> v;
    return v;
}

template <typename T1 = default_type, typename T2 = default_type>
std::vector<std::pair<T1, T2>> read_vec_pair() {
    int n;
    std::cin >> n;
    return read_vec_pair<T1, T2>(n);
}

template <typename... Args>
std::vector<std::tuple<Args...>> read_vec_tuple(int n) {
    std::vector<std::tuple<Args...>> v(n);
    std::cin >> v;
    return v;
}

template <typename... Args>
std::vector<std::tuple<Args...>> read_vec_tuple() {
    int n;
    std::cin >> n;
    return read_vec_tuple<Args...>(n);
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid(int h, int w) {
    std::vector<std::vector<T>> grid(h, std::vector<T>(w));
    std::cin >> grid;
    return grid;
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid() {
    int h, w;
    std::cin >> h >> w;
    return read_vec_grid<T>(h, w);
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_var(int n) {
    std::vector<std::vector<T>> res(n);
    for (int i = 0; i < n; ++i) {
        int m;
        std::cin >> m;
        res[i] = read_vec<T>(m);
    }
    return res;
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_var() {
    int n;
    std::cin >> n;
    return read_vec_var<T>(n);
}

template <typename T = default_type>
T read_zero_idx() {
    T val;
    std::cin >> val;
    return val - 1;
}

inline std::vector<std::vector<int>> read_graph(int n, int m, bool directed = false) {
    std::vector<std::vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int u = read_zero_idx<int>();
        int v = read_zero_idx<int>();
        g[u].push_back(v);
        if (!directed) {
            g[v].push_back(u);
        }
    }
    return g;
}

inline std::vector<std::vector<int>> read_graph(bool directed = false) {
    int n, m;
    std::cin >> n >> m;
    return read_graph(n, m, directed);
}

#include <istream>
#include <numeric>
#include <print>
#include <vector>

#define ALL(a) (a).begin(), (a).end()
using i128 = __int128;

template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <std::integral T>
inline T div_ceil(T a, T b) {
    if (a > 0) return a / b + (a % b != 0);
    return a / b;
}

template <std::integral T>
inline T div_floor(T a, T b) {
    if (a < 0) return a / b - (a % b != 0);
    return a / b;
}

template <std::integral T>
inline T mod(T a, T m) {
    a %= m;
    if (a < 0) a += m;
    return a;
}

template <typename T>
inline constexpr T INF = std::numeric_limits<T>::max() / 2;

template <>
inline constexpr float INF<float> = std::numeric_limits<float>::infinity();

template <>
inline constexpr double INF<double> = std::numeric_limits<double>::infinity();

template <>
inline constexpr long double INF<long double> = std::numeric_limits<long double>::infinity();

template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
    std::vector<T> v(n);
    std::iota(v.begin(), v.end(), start);
    return v;
}

template <typename T>
inline std::vector<T> doubled_vec(const std::vector<T>& v) {
    std::vector<T> res;
    res.reserve(v.size() * 2);
    res.insert(res.end(), v.begin(), v.end());
    res.insert(res.end(), v.begin(), v.end());
    return res;
}

inline void Yes(bool b = true) {
    std::println("{}", (b ? "Yes" : "No"));
}

inline void No() {
    std::println("No");
}

#ifdef LOCAL
#include <utility/debug.hpp>
#else
#define debug(...)
#endif

#include <algorithm>
#include <bit>
#include <cassert>
#include <vector>

struct FunctionalGraph {
    int n;
    int log_k;
    std::vector<int> to;
    std::vector<int> cycle_id;
    std::vector<int> cycle_pos;
    std::vector<std::vector<int>> cycles;
    std::vector<int> root;
    std::vector<int> depth;
    std::vector<std::vector<int>> doubling;
    std::vector<std::vector<int>> children;
    bool is_built = false;

    std::vector<long long> tree_pref;
    std::vector<std::vector<long long>> cycle_pref;
    std::vector<long long> cycle_sum;
    bool has_weight = false;

    explicit FunctionalGraph(int n, const std::vector<int>& to)
        : n(n), to(to), cycle_id(n, -1), cycle_pos(n, -1), root(n, -1), depth(n, 0) {
        log_k = std::max(1, std::bit_width(static_cast<unsigned int>(n)));
    }

    void build() {
        std::vector<int> state(n, 0);
        std::vector<int> path;

        for (int i = 0; i < n; i++) {
            if (state[i] != 0) continue;

            int curr = i;
            path.clear();
            while (state[curr] == 0) {
                state[curr] = 1;
                path.push_back(curr);
                curr = to[curr];
            }

            if (state[curr] == 1) {

                std::vector<int> cycle;
                bool in_cycle = false;
                for (int v : path) {
                    if (v == curr) in_cycle = true;
                    if (in_cycle) {
                        cycle_id[v] = cycles.size();
                        cycle_pos[v] = cycle.size();
                        root[v] = v;
                        depth[v] = 0;
                        cycle.push_back(v);
                    }
                }
                cycles.push_back(cycle);
            }

            for (int j = static_cast<int>(path.size()) - 1; j >= 0; j--) {
                int u = path[j];
                state[u] = 2;
                if (root[u] == -1) {
                    int next_v = to[u];
                    root[u] = root[next_v];
                    depth[u] = depth[next_v] + 1;
                }
            }
        }

        children.assign(n, {});
        for (int i = 0; i < n; i++) {
            if (cycle_id[i] == -1) {
                children[to[i]].push_back(i);
            }
        }

        doubling.assign(log_k, std::vector<int>(n));
        for (int i = 0; i < n; i++) doubling[0][i] = to[i];

        for (int k = 0; k < log_k - 1; k++) {
            for (int i = 0; i < n; i++) {
                doubling[k + 1][i] = doubling[k][doubling[k][i]];
            }
        }
        is_built = true;
    }

    template <typename T>
    void build_weight(const std::vector<T>& weight) {
        assert(is_built && "You must call build() before calling build_weight().");
        assert(static_cast<int>(weight.size()) == n);
        tree_pref.assign(n, 0);
        int num_cycles = cycles.size();
        cycle_pref.assign(num_cycles, {});
        cycle_sum.assign(num_cycles, 0);

        for (int cid = 0; cid < num_cycles; cid++) {
            for (int r : cycles[cid]) {
                tree_pref[r] = 0;
                std::vector<int> q = {r};
                int head = 0;
                while (head < static_cast<int>(q.size())) {
                    int p = q[head++];
                    for (int c : children[p]) {

                        tree_pref[c] = tree_pref[p] + static_cast<long long>(weight[c]);
                        q.push_back(c);
                    }
                }
            }
        }

        for (int cid = 0; cid < num_cycles; cid++) {
            int sz = cycles[cid].size();
            cycle_pref[cid].assign(sz + 1, 0);
            for (int i = 0; i < sz; i++) {
                int v = cycles[cid][i];
                cycle_pref[cid][i + 1] = cycle_pref[cid][i] + static_cast<long long>(weight[v]);
                cycle_sum[cid] += static_cast<long long>(weight[v]);
            }
        }
        has_weight = true;
    }

    int jump(int u, long long k) const {
        assert(is_built && "You must call build() before using jump().");
        if (k <= depth[u]) {

            for (int i = 0; k > 0; i++, k >>= 1) {
                if (k & 1) u = doubling[i][u];
            }
            return u;
        }

        k -= depth[u];
        int r = root[u];
        int cid = cycle_id[r];
        int c_size = cycles[cid].size();
        return cycles[cid][(cycle_pos[r] + k) % c_size];
    }

    long long path_sum(int u, long long k) const {
        assert(has_weight && "build_weight must be called before evaluating path_sum");
        if (k <= 0) return 0;

        long long ans = 0;
        if (k <= depth[u]) {

            int v = jump(u, k);

            ans = tree_pref[u] - tree_pref[v];
        } else {

            ans += tree_pref[u];
            k -= depth[u];

            int r = root[u];
            int cid = cycle_id[r];
            long long sz = cycles[cid].size();

            long long loops = k / sz;
            ans += loops * cycle_sum[cid];

            int rem = k % sz;
            if (rem > 0) {
                int start_idx = cycle_pos[r];
                if (start_idx + rem <= sz) {

                    ans += cycle_pref[cid][start_idx + rem] - cycle_pref[cid][start_idx];
                } else {

                    ans += cycle_pref[cid][sz] - cycle_pref[cid][start_idx];
                    ans += cycle_pref[cid][(start_idx + rem) % sz];
                }
            }
        }
        return ans;
    }

    long long dist(int u, int v) const {
        assert(is_built && "You must call build() before using dist().");
        if (root[u] != root[v]) {

            if (cycle_id[root[u]] != cycle_id[root[v]]) return -1;

            if (cycle_id[v] == -1) return -1;
        }

        if (cycle_id[v] == -1) {

            if (depth[u] < depth[v]) return -1;
            int diff = depth[u] - depth[v];
            if (jump(u, diff) == v) return diff;
            return -1;
        } else {

            long long d = depth[u];
            int r_u = root[u];
            int c_size = get_cycle_size(r_u);
            int diff_cycle = (cycle_pos[v] - cycle_pos[r_u] + c_size) % c_size;
            return d + diff_cycle;
        }
    }

    int get_cycle_size(int u) const {
        assert(is_built && "You must call build() before using get_cycle_size().");
        return cycles[cycle_id[root[u]]].size();
    }

    bool on_cycle(int u) const {
        assert(is_built && "You must call build() before using on_cycle().");
        return cycle_id[u] != -1;
    }

    int dist_to_cycle(int u) const {
        assert(is_built && "You must call build() before using dist_to_cycle().");
        return depth[u];
    }
};

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    read(N);
    auto A = read_vec<int>(N);
    for (auto& a : A)
        a--;
    FunctionalGraph fg(N, A);
    fg.build();
    auto vec = fg.cycle_id;
    debug(vec);
    int mx = *ranges::max_element(vec);
    println("{}", mx + 1);
}

int main() {
    solve();
}