This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C" #include "../../template.h" #include "../LCA.h" void solve() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<vector<int>> adj(n); REP(i,n) { int k; cin >> k; while (k--) { int j; cin >> j; adj[i].push_back(j); adj[j].push_back(i); } } LCA lca(n, adj, 0); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; cout << lca.lca(u, v) << '\n'; } }
#line 1 "DataStructure/test/aizu_grl_5_c_lca.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_5_C" #line 1 "template.h" #include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define EACH(it,a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it) #define DEBUG(x) { cout << #x << " = "; cout << (x) << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } #define sqr(x) ((x) * (x)) // For printing pair, container, etc. // Copied from https://quangloc99.github.io/2021/07/30/my-CP-debugging-template.html template<class U, class V> ostream& operator << (ostream& out, const pair<U, V>& p) { return out << '(' << p.first << ", " << p.second << ')'; } template<class Con, class = decltype(begin(declval<Con>()))> typename enable_if<!is_same<Con, string>::value, ostream&>::type operator << (ostream& out, const Con& con) { out << '{'; for (auto beg = con.begin(), it = beg; it != con.end(); it++) { out << (it == beg ? "" : ", ") << *it; } return out << '}'; } template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) { if constexpr(i == tuple_size<T>::value) return out << ")"; else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); } template<class ...U> ostream& operator << (ostream& out, const tuple<U...>& t) { return print_tuple_utils<0, tuple<U...>>(out, t); } mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); long long get_rand(long long r) { return uniform_int_distribution<long long> (0, r-1)(rng); } template<typename T> vector<T> read_vector(int n) { vector<T> res(n); for (int& x : res) cin >> x; return res; } void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; } #line 1 "DataStructure/LCA.h" // LCA // Notes: // - Index from 0 // - Cannot use for queries like min edge in path u -> v // // Tested: // - https://judge.yosupo.jp/problem/lca #line 1 "DataStructure/RMQ.h" // RMQ {{{ // // Sparse table // Usage: // RMQ<int, _min> st(v); // // Note: // - doesn't work for empty range // // Tested: // - https://judge.yosupo.jp/problem/staticrmq template<class T, T (*op) (T, T)> struct RMQ { RMQ() = default; RMQ(const vector<T>& v) : t{v}, n{(int) v.size()} { for (int k = 1; (1<<k) <= n; ++k) { t.emplace_back(n - (1<<k) + 1); for (int i = 0; i + (1<<k) <= n; ++i) { t[k][i] = op(t[k-1][i], t[k-1][i + (1<<(k-1))]); } } } // get range [l, r-1] // doesn't work for empty range T get(int l, int r) const { assert(0 <= l && l < r && r <= n); int k = __lg(r - l); return op(t[k][l], t[k][r - (1<<k)]); } private: vector<vector<T>> t; int n; }; template<class T> T _min(T a, T b) { return b < a ? b : a; } template<class T> T _max(T a, T b) { return a < b ? b : a; } // }}} #line 9 "DataStructure/LCA.h" struct LCA { const int n; vector<vector<int>> adj; const int root; using P = pair<int,int>; static P f(P x, P y) { return std::min(x, y); } LCA(int _n, const vector<vector<int>>& _adj, int _root) : n(_n), adj(_adj), root(_root) { assert(0 <= root && root < n); id.resize(n); depth.resize(n); order.reserve(2 * n); dfs(root, -1, 0); rmq = RMQ<P, f>(order); } int lca(int u, int v) { assert(0 <= u && u < n); assert(0 <= v && v < n); int x = id[u], y = id[v]; if (x > y) std::swap(x, y); return rmq.get(x, y+1).second; } // private: vector<int> id, depth; vector<P> order; RMQ<P, f> rmq; void dfs(int u, int fu, int d) { id[u] = order.size(); depth[u] = d; order.emplace_back(d, u); for (int v : adj[u]) { if (v == fu) continue; dfs(v, u, d + 1); order.emplace_back(d, u); } } }; #line 5 "DataStructure/test/aizu_grl_5_c_lca.test.cpp" void solve() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector<vector<int>> adj(n); REP(i,n) { int k; cin >> k; while (k--) { int j; cin >> j; adj[i].push_back(j); adj[j].push_back(i); } } LCA lca(n, adj, 0); int q; cin >> q; while (q--) { int u, v; cin >> u >> v; cout << lca.lca(u, v) << '\n'; } }