sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "graph/manhattan_mst.hpp"
2次元平面上に点が与えられ,各点の間にそのマンハッタン距離の重みを持つ辺が張られているとき,最小全域木を計算する.
vector<T, Edge<T>> manhattan_mst(vector<pair<T, T>> pts)
pts
#pragma once #include <algorithm> #include <limits> #include <vector> #include "../data-structure/segtree/segment_tree.hpp" #include "../graph/mst.hpp" template <typename U> struct MinMonoid { using T = std::pair<U, int>; static T id() { return {std::numeric_limits<U>::max(), -1}; } static T op(T a, T b) { return std::min(a, b); } }; template <typename T> std::pair<T, std::vector<std::pair<int, int>>> manhattan_mst( std::vector<std::pair<T, T>> pts) { std::vector<int> idx(pts.size()); std::iota(idx.begin(), idx.end(), 0); std::vector<std::tuple<int, int, T>> edges; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { // sort by y-x asc then by y desc std::ranges::sort(idx, {}, [&](int i) { auto [x, y] = pts[i]; return std::make_tuple(y - x, -y, i); }); // compress y std::vector<T> cs; cs.reserve(pts.size()); for (auto [x, y] : pts) cs.push_back(y); std::ranges::sort(cs); cs.erase(std::ranges::unique(cs).begin(), cs.end()); // sweep SegmentTree<MinMonoid<T>> st(cs.size()); for (int i : idx) { auto [x, y] = pts[i]; int k = std::ranges::lower_bound(cs, y) - cs.begin(); auto [d, j] = st.fold(k, cs.size()); if (j != -1) { edges.push_back({i, j, d - (x + y)}); } st.update(k, {x + y, i}); } for (auto& p : pts) std::swap(p.first, p.second); } for (auto& p : pts) p.first *= -1; } for (auto& p : pts) p.second *= -1; } auto [weight, mst_edges] = kruskal(edges, pts.size()); std::vector<std::pair<int, int>> ret(mst_edges.size()); std::ranges::transform(mst_edges, ret.begin(), [&](const auto& e) { return std::make_pair(std::get<0>(e), std::get<1>(e)); }); return {weight, ret}; }
#line 2 "graph/manhattan_mst.hpp" #include <algorithm> #include <limits> #include <vector> #line 3 "data-structure/segtree/segment_tree.hpp" #include <bit> #line 5 "data-structure/segtree/segment_tree.hpp" template <typename M> class SegmentTree { using T = M::T; public: SegmentTree() = default; explicit SegmentTree(int n) : SegmentTree(std::vector<T>(n, M::id())) {} explicit SegmentTree(const std::vector<T>& v) : size(std::bit_ceil(v.size())), node(2 * size, M::id()) { std::ranges::copy(v, node.begin() + size); for (int i = size - 1; i > 0; --i) { node[i] = M::op(node[2 * i], node[2 * i + 1]); } } T operator[](int k) const { return node[k + size]; } void update(int k, const T& x) { k += size; node[k] = x; while (k >>= 1) node[k] = M::op(node[2 * k], node[2 * k + 1]); } T fold(int l, int r) const { T vl = M::id(), vr = M::id(); for (l += size, r += size; l < r; l >>= 1, r >>= 1) { if (l & 1) vl = M::op(vl, node[l++]); if (r & 1) vr = M::op(node[--r], vr); } return M::op(vl, vr); } template <typename F> int find_first(int l, F cond) const { T v = M::id(); for (l += size; l > 0; l >>= 1) { if (l & 1) { T nv = M::op(v, node[l]); if (cond(nv)) { while (l < size) { nv = M::op(v, node[2 * l]); if (cond(nv)) { l = 2 * l; } else { v = nv, l = 2 * l + 1; } } return l + 1 - size; } v = nv; ++l; } } return -1; } template <typename F> int find_last(int r, F cond) const { T v = M::id(); for (r += size; r > 0; r >>= 1) { if (r & 1) { --r; T nv = M::op(node[r], v); if (cond(nv)) { while (r < size) { nv = M::op(node[2 * r + 1], v); if (cond(nv)) { r = 2 * r + 1; } else { v = nv, r = 2 * r; } } return r - size; } v = nv; } } return -1; } private: int size; std::vector<T> node; }; #line 3 "graph/mst.hpp" #include <queue> #include <utility> #line 6 "graph/mst.hpp" #line 4 "data-structure/unionfind/union_find.hpp" class UnionFind { public: UnionFind() = default; explicit UnionFind(int n) : data(n, -1) {} int find(int x) { if (data[x] < 0) return x; return data[x] = find(data[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (data[x] > data[y]) std::swap(x, y); data[x] += data[y]; data[y] = x; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -data[find(x)]; } private: std::vector<int> data; }; #line 8 "graph/mst.hpp" template <typename T> using Edge = std::tuple<int, int, T>; /* * Kruskal's Algorithm */ template <typename T> std::pair<T, std::vector<Edge<T>>> kruskal(std::vector<Edge<T>> G, int V) { std::ranges::sort(G, {}, [](auto& e) { return std::get<2>(e); }); UnionFind uf(V); T weight = 0; std::vector<Edge<T>> edges; for (auto& [u, v, w] : G) { if (!uf.same(u, v)) { uf.unite(u, v); weight += w; edges.push_back({u, v, w}); } } return {weight, edges}; } /* * Prim's Algorithm */ template <typename T> std::pair<T, std::vector<Edge<T>>> prim( const std::vector<std::vector<std::pair<int, T>>>& G) { std::vector<bool> used(G.size()); auto cmp = [](const auto& e1, const auto& e2) { return std::get<2>(e1) > std::get<2>(e2); }; std::priority_queue<Edge<T>, std::vector<Edge<T>>, decltype(cmp)> pq(cmp); pq.emplace(0, 0, 0); T weight = 0; std::vector<Edge<T>> edges; while (!pq.empty()) { auto [p, v, w] = pq.top(); pq.pop(); if (used[v]) continue; used[v] = true; weight += w; if (v != 0) edges.push_back({p, v, w}); for (auto& [u, w2] : G[v]) { pq.emplace(v, u, w2); } } return {weight, edges}; } /* * Boruvka's Algorithm */ template <typename T> std::pair<T, std::vector<Edge<T>>> boruvka(std::vector<Edge<T>> G, int V) { UnionFind uf(V); T weight = 0; std::vector<Edge<T>> edges; while (uf.size(0) < V) { std::vector<Edge<T>> cheapest(V, {-1, -1, std::numeric_limits<T>::max()}); for (auto [u, v, w] : G) { if (!uf.same(u, v)) { u = uf.find(u); v = uf.find(v); if (w < std::get<2>(cheapest[u])) cheapest[u] = {u, v, w}; if (w < std::get<2>(cheapest[v])) cheapest[v] = {u, v, w}; } } for (auto [u, v, w] : cheapest) { if (u != -1 && !uf.same(u, v)) { uf.unite(u, v); weight += w; edges.push_back({u, v, w}); } } } return {weight, edges}; } #line 8 "graph/manhattan_mst.hpp" template <typename U> struct MinMonoid { using T = std::pair<U, int>; static T id() { return {std::numeric_limits<U>::max(), -1}; } static T op(T a, T b) { return std::min(a, b); } }; template <typename T> std::pair<T, std::vector<std::pair<int, int>>> manhattan_mst( std::vector<std::pair<T, T>> pts) { std::vector<int> idx(pts.size()); std::iota(idx.begin(), idx.end(), 0); std::vector<std::tuple<int, int, T>> edges; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 2; ++j) { for (int k = 0; k < 2; ++k) { // sort by y-x asc then by y desc std::ranges::sort(idx, {}, [&](int i) { auto [x, y] = pts[i]; return std::make_tuple(y - x, -y, i); }); // compress y std::vector<T> cs; cs.reserve(pts.size()); for (auto [x, y] : pts) cs.push_back(y); std::ranges::sort(cs); cs.erase(std::ranges::unique(cs).begin(), cs.end()); // sweep SegmentTree<MinMonoid<T>> st(cs.size()); for (int i : idx) { auto [x, y] = pts[i]; int k = std::ranges::lower_bound(cs, y) - cs.begin(); auto [d, j] = st.fold(k, cs.size()); if (j != -1) { edges.push_back({i, j, d - (x + y)}); } st.update(k, {x + y, i}); } for (auto& p : pts) std::swap(p.first, p.second); } for (auto& p : pts) p.first *= -1; } for (auto& p : pts) p.second *= -1; } auto [weight, mst_edges] = kruskal(edges, pts.size()); std::vector<std::pair<int, int>> ret(mst_edges.size()); std::ranges::transform(mst_edges, ret.begin(), [&](const auto& e) { return std::make_pair(std::get<0>(e), std::get<1>(e)); }); return {weight, ret}; }