diff options
Diffstat (limited to 'content/graph/LCA_sparse.cpp')
| -rw-r--r-- | content/graph/LCA_sparse.cpp | 14 |
1 files changed, 7 insertions, 7 deletions
diff --git a/content/graph/LCA_sparse.cpp b/content/graph/LCA_sparse.cpp index 221b5ed..1da8876 100644 --- a/content/graph/LCA_sparse.cpp +++ b/content/graph/LCA_sparse.cpp @@ -5,12 +5,12 @@ struct LCA { SparseTable st; //sparse table @\sourceref{datastructures/sparseTable.cpp}@ void init(vector<vector<int>>& adj, int root) { - depth.assign(2 * sz(adj), 0); - visited.assign(2 * sz(adj), -1); - first.assign(sz(adj), 2 * sz(adj)); + depth.assign(2 * ssize(adj), 0); + visited.assign(2 * ssize(adj), -1); + first.assign(ssize(adj), 2 * ssize(adj)); idx = 0; dfs(adj, root); - st.init(&depth); + st.init(depth); } void dfs(vector<vector<int>>& adj, int v, ll d=0) { @@ -18,15 +18,15 @@ struct LCA { first[v] = min(idx, first[v]), idx++; for (int u : adj[v]) { - if (first[u] == 2 * sz(adj)) { + if (first[u] == 2 * ssize(adj)) { dfs(adj, u, d + 1); visited[idx] = v, depth[idx] = d, idx++; }}} int getLCA(int u, int v) { if (first[u] > first[v]) swap(u, v); - return visited[st.queryIdempotent(first[u], first[v] + 1)]; + return visited[st.query(first[u], first[v] + 1)]; } - ll getDepth(int v) {return depth[first[v]];} + ll getDepth(int v) { return depth[first[v]]; } }; |