Open Astral-23 opened 2 months ago
#include "../Datastructure/dsu.hpp" #include "../Datastructure/dsu.hpp" struct functional_graph { int n; int d = 30; vec<int> sz, to, leader; vec<bool> on_cycle; vec<vec<int>> cycle, db; dsu uf; bool f = false; functional_graph(vec<int> &TO) : to(TO) { n = to.size(); sz = leader = vec<int>(n); cycle.resize(n); on_cycle.resize(n, false); db.resize(d); uf = dsu(n); rep(i, 0, n) uf.merge(i, to[i]); vec<bool> seen(n, false); rep(i, 0, n) { int r = uf.leader(i); if(seen[r] == false) { seen[r] = true; sz[r] = uf.size(r); int v = r; rep(j, 0, uf.size(r)) v = to[v]; int s = v; do { cycle[r].push_back(v); on_cycle[v] = true; v = to[v]; } while (v != s); } } rep(i, 0, n) leader[i] = uf.leader(i); } int jump(int p, ll k) { if(f == false) { f = true; db[0] = to; rep(t, 1, d) { rep(i, 0, n) { db[t][i] = db[t-1][db[t-1][i]]; } } } rep(i, 0, d) if(k >> i & 1) { p = db[i][p]; } return p; } };
jumpはverifyしてない help! https://atcoder.jp/contests/abc357/submissions/54550056
jumpはverifyしてない help! https://atcoder.jp/contests/abc357/submissions/54550056