Solutions of Graph query - MarisaOJ: Marisa Online Judge

Solutions of Graph query

Select solution language

Write solution here.


User Avatar nihahaha    Created at    9 likes

Đây là một bài toán bảng thưa khá cơ bản, bạn có thể đọc thêm về cách cài đặt ở [đây.](https://wiki.vnoi.info/vi/algo/data-structures/rmq) **Thuật toán:** - Gọi $f(u, k)$ là đỉnh kết thúc khi bắt đầu từ đỉnh u và đi $2^k$ bước. Dễ thấy có thể tính trước giá trị này qua công thức $f(u, k) = f(f(u, k-1), k-1))$ với mọi $k > 0$, với $f(u, 0)$ là đỉnh mà u có cạnh ra nối tới. - Khi đó, với mỗi truy vấn dạng $(u, x)$, ta sẽ chuyển từ đỉnh $u$ đến $f(u, k)$ với mọi bit $k$ bật trong biểu diễn nhị phân của $x$. Độ phức tạp của thuật toán là $O(32(n+q))$, do ta phải chuyển trạng thái tối đa $32$ lần (vì $log(10^9) = 32$). ***Lưu ý! Bài này chỉ áp dụng cho trường hợp mỗi đỉnh có tối đa 1 cạnh ra, do chỉ khi đó ta mới biết được chắc chắn mình sẽ đi hướng nào.*** **Code mẫu:** ```cpp #include<bits/stdc++.h> #define fu(i, a, b) for(int i = (a); i < (b); i++) #define fub(i, a, b) for(int i = (a); i <= (b); i++) #define fastio ios_base::sync_with_stdio(0); cin.tie(0); using namespace std; const int lim = 1e18; const int N = 1e5 + 5; const int M = 1e9 + 7; const int LG = 31; int n, q; int to[N]; int nxt[LG][N]; void sparse(int n){ fub(i, 1, n){ nxt[0][i] = to[i]; } fu(i, 1, LG)fub(j, 1, n)nxt[i][j] = nxt[i-1][nxt[i-1][j]]; } int des(int u, int x){ fu(i, 0, LG){ if((x >> i)&1)u = nxt[i][u]; } return u; } signed main(){ fastio; cin >> n >> q; fub(i, 1, n)cin >> to[i]; sparse(n); fub(i, 1, q){ int u, x; cin >> u >> x; cout << des(u, x) << '\n'; } }