library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub firiexp/library

:heavy_check_mark: test/aoj0403.test.cpp

Depends on

Code

#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0403"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#include "../graph/manhattanmst.cpp"
#include "../datastructure/unionfind.cpp"

int main() {
    int n;
    cin >> n;
    vector<int> xs(n), ys(n);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        xs[i] = x+y, ys[i] = x-y;
    }
    auto res = manhattanMST(xs, ys);
    vector<pair<int, pair<int, int>>> r(res.size());
    for (int i = 0; i < res.size(); ++i) {
        auto &&x = res[i];
        r[i] = {abs(xs[x.first]-xs[x.second])+abs(ys[x.first]-ys[x.second]), {x.first, x.second}};
    }
    sort(r.begin(),r.end());
    UnionFind uf(n);
    ll ans = 0;
    for (auto &&i : r) {
        pair<int, int> p; tie(ignore, p) = i;
        if(uf.unite(p.first, p.second)) ans += i.first;
    }
    cout << ans/2 << "\n";
    return 0;
}
#line 1 "test/aoj0403.test.cpp"
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Final/0403"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using uint = unsigned;
using ull = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

#line 1 "graph/manhattanmst.cpp"
template<typename T>
vector<pair<int, int>> manhattanMST(vector<T> xs, vector<T> ys) {
    using P = pair<int, int>;
    vector<P> es;
    vector<int> ord(xs.size());
    for (int s = 0; s < 4; s++) {
        iota(ord.begin(), ord.end(), 0);
        auto cmp = [&](int i, int j) -> bool {
            if (xs[i]+ys[i] != xs[j]+ys[j]) return xs[i]+ys[i] < xs[j]+ys[j];
            return (s>>1) ^ (i > j);
        };
        sort(ord.begin(), ord.end(), cmp);
        map<pair<T, int>, int> idx;
        for (auto &&i : ord) {
            pair<T, int> p = {-ys[i], (s == 3)?i:-i};
            for (auto it = idx.lower_bound(p); it != idx.end(); it = idx.erase(it)) {
                if (xs[i] - xs[it->second] < ys[i] - ys[it->second]) break;
                es.emplace_back(i, it->second);
            }
            idx[p] = i;
        }
        swap(xs, ys);
        if(s&1) for(auto &&i : xs) i = -i;
    }
    return es;
}
#line 1 "datastructure/unionfind.cpp"
class UnionFind {
    int n;
    vector<int> uni;
    int forest_size;
public:
    explicit UnionFind(int n) : n(n), uni(static_cast<uint>(n), -1), forest_size(n) {};

    int root(int a){
        if (uni[a] < 0) return a;
        else return (uni[a] = root(uni[a]));
    }

    bool unite(int a, int b) {
        a = root(a);
        b = root(b);
        if(a == b) return false;
        if(uni[a] > uni[b]) swap(a, b);
        uni[a] += uni[b];
        uni[b] = a;
        forest_size--;
        return true;
    }
    int size(){ return forest_size; }
    int size(int i){ return -uni[root(i)]; }
    bool same(int a, int b) { return root(a) == root(b); }
};

/**
 * @brief UnionFind(素集合データ構造)
 * @docs _md/unionfind.md
 */
#line 22 "test/aoj0403.test.cpp"

int main() {
    int n;
    cin >> n;
    vector<int> xs(n), ys(n);
    for (int i = 0; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        xs[i] = x+y, ys[i] = x-y;
    }
    auto res = manhattanMST(xs, ys);
    vector<pair<int, pair<int, int>>> r(res.size());
    for (int i = 0; i < res.size(); ++i) {
        auto &&x = res[i];
        r[i] = {abs(xs[x.first]-xs[x.second])+abs(ys[x.first]-ys[x.second]), {x.first, x.second}};
    }
    sort(r.begin(),r.end());
    UnionFind uf(n);
    ll ans = 0;
    for (auto &&i : r) {
        pair<int, int> p; tie(ignore, p) = i;
        if(uf.unite(p.first, p.second)) ans += i.first;
    }
    cout << ans/2 << "\n";
    return 0;
}
Back to top page