This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub hitonanode/cplib-cpp
#define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst" #include "../manhattan_mst.hpp" #include "../../unionfind/unionfind.hpp" #include <iostream> using namespace std; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector<int> xs(N), ys(N); for (int i = 0; i < N; i++) cin >> xs[i] >> ys[i]; UnionFind uf(N); long long weight = 0; vector<pair<int, int>> edges; for (auto [w, i, j] : manhattan_mst(xs, ys)) { if (uf.unite(i, j)) { weight += w; edges.emplace_back(i, j); } } cout << weight << '\n'; for (auto p : edges) cout << p.first << ' ' << p.second << '\n'; }
#line 1 "graph/test/manhattan_mst.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/manhattanmst" #line 2 "graph/manhattan_mst.hpp" #include <algorithm> #include <map> #include <numeric> #include <tuple> #include <vector> // CUT begin // Manhattan MST: 二次元平面上の頂点たちのマンハッタン距離による minimum spanning tree の O(N) 本の候補辺を列挙 // Complexity: O(N log N) // output: [(weight_uv, u, v), ...] // Verified: https://judge.yosupo.jp/problem/manhattanmst, https://www.codechef.com/problems/HKRMAN // Reference: // [1] H. Zhou, N. Shenoy, W. Nicholls, // "Efficient minimum spanning tree construction without Delaunay triangulation," // Information Processing Letters, 81(5), 271-276, 2002. template <typename T> std::vector<std::tuple<T, int, int>> manhattan_mst(std::vector<T> xs, std::vector<T> ys) { const int n = xs.size(); std::vector<int> idx(n); std::iota(idx.begin(), idx.end(), 0); std::vector<std::tuple<T, int, int>> ret; for (int s = 0; s < 2; s++) { for (int t = 0; t < 2; t++) { auto cmp = [&](int i, int j) { return xs[i] + ys[i] < xs[j] + ys[j]; }; std::sort(idx.begin(), idx.end(), cmp); std::map<T, int> sweep; for (int i : idx) { for (auto it = sweep.lower_bound(-ys[i]); it != sweep.end(); it = sweep.erase(it)) { int j = it->second; if (xs[i] - xs[j] < ys[i] - ys[j]) break; ret.emplace_back(std::abs(xs[i] - xs[j]) + std::abs(ys[i] - ys[j]), i, j); } sweep[-ys[i]] = i; } std::swap(xs, ys); } for (auto &x : xs) x = -x; } std::sort(ret.begin(), ret.end()); return ret; } #line 4 "unionfind/unionfind.hpp" #include <utility> #line 6 "unionfind/unionfind.hpp" // CUT begin // UnionFind Tree (0-indexed), based on size of each disjoint set struct UnionFind { std::vector<int> par, cou; UnionFind(int N = 0) : par(N), cou(N, 1) { iota(par.begin(), par.end(), 0); } int find(int x) { return (par[x] == x) ? x : (par[x] = find(par[x])); } bool unite(int x, int y) { x = find(x), y = find(y); if (x == y) return false; if (cou[x] < cou[y]) std::swap(x, y); par[y] = x, cou[x] += cou[y]; return true; } int count(int x) { return cou[find(x)]; } bool same(int x, int y) { return find(x) == find(y); } std::vector<std::vector<int>> groups() { std::vector<std::vector<int>> ret(par.size()); for (int i = 0; i < int(par.size()); ++i) ret[find(i)].push_back(i); ret.erase(std::remove_if(ret.begin(), ret.end(), [&](const std::vector<int> &v) { return v.empty(); }), ret.end()); return ret; } }; #line 4 "graph/test/manhattan_mst.test.cpp" #include <iostream> using namespace std; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N; cin >> N; vector<int> xs(N), ys(N); for (int i = 0; i < N; i++) cin >> xs[i] >> ys[i]; UnionFind uf(N); long long weight = 0; vector<pair<int, int>> edges; for (auto [w, i, j] : manhattan_mst(xs, ys)) { if (uf.unite(i, j)) { weight += w; edges.emplace_back(i, j); } } cout << weight << '\n'; for (auto p : edges) cout << p.first << ' ' << p.second << '\n'; }