test/aoj/1337/main.test.cpp
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1337"
#include <iostream>
#include <vector>
#include "Mylib/DataStructure/UnionFind/unionfind.cpp"
#include "Mylib/IO/input_tuple_vector.cpp"
#include "Mylib/Utils/compressor.cpp"
namespace hl = haar_lib;
const int H = 200;
const int W = 200;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n;
while (std::cin >> n, n) {
auto [l, t, r, b] = hl::input_tuple_vector<int, int, int, int>(n);
int64_t a[H][W] = {};
hl::compressor_builder<int>().add(l, r, -1).build().compress(l, r);
hl::compressor_builder<int>().add(t, b, -1).build().compress(t, b);
for (int i = 0; i < n; ++i) {
for (int x = l[i]; x < r[i]; ++x) {
for (int y = b[i]; y < t[i]; ++y) {
a[x][y] |= (1LL << i);
}
}
}
hl::unionfind uf(H * W);
int index[H][W];
{
int k = 0;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
index[i][j] = k;
++k;
}
}
}
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
if (i + 1 < H and a[i][j] == a[i + 1][j]) uf.merge(index[i][j], index[i + 1][j]);
if (j + 1 < W and a[i][j] == a[i][j + 1]) uf.merge(index[i][j], index[i][j + 1]);
}
}
int ans = uf.count_groups();
std::cout << ans << "\n";
}
return 0;
}
#line 1 "test/aoj/1337/main.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1337"
#include <iostream>
#include <vector>
#line 2 "Mylib/DataStructure/UnionFind/unionfind.cpp"
#include <algorithm>
#include <numeric>
#line 5 "Mylib/DataStructure/UnionFind/unionfind.cpp"
namespace haar_lib {
class unionfind {
int n_, count_;
mutable std::vector<int> parent_;
std::vector<int> depth_, size_;
public:
unionfind() {}
unionfind(int n) : n_(n), count_(n), parent_(n), depth_(n, 1), size_(n, 1) {
std::iota(parent_.begin(), parent_.end(), 0);
}
int root_of(int i) const {
if (parent_[i] == i)
return i;
else
return parent_[i] = root_of(parent_[i]);
}
bool is_same(int i, int j) const { return root_of(i) == root_of(j); }
int merge(int i, int j) {
const int ri = root_of(i), rj = root_of(j);
if (ri == rj)
return ri;
else {
--count_;
if (depth_[ri] < depth_[rj]) {
parent_[ri] = rj;
size_[rj] += size_[ri];
return rj;
} else {
parent_[rj] = ri;
size_[ri] += size_[rj];
if (depth_[ri] == depth_[rj]) ++depth_[ri];
return ri;
}
}
}
int size_of(int i) const { return size_[root_of(i)]; }
int count_groups() const { return count_; }
auto get_groups() const {
std::vector<std::vector<int>> ret(n_);
for (int i = 0; i < n_; ++i) {
ret[root_of(i)].push_back(i);
}
ret.erase(
std::remove_if(
ret.begin(), ret.end(),
[](const auto &a) { return a.empty(); }),
ret.end());
return ret;
}
};
} // namespace haar_lib
#line 2 "Mylib/IO/input_tuple_vector.cpp"
#include <initializer_list>
#line 4 "Mylib/IO/input_tuple_vector.cpp"
#include <tuple>
#include <utility>
#line 7 "Mylib/IO/input_tuple_vector.cpp"
namespace haar_lib {
template <typename T, size_t... I>
void input_tuple_vector_init(T &val, int N, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::get<I>(val).resize(N)), 0)...};
}
template <typename T, size_t... I>
void input_tuple_vector_helper(T &val, int i, std::index_sequence<I...>) {
(void) std::initializer_list<int>{(void(std::cin >> std::get<I>(val)[i]), 0)...};
}
template <typename... Args>
auto input_tuple_vector(int N) {
std::tuple<std::vector<Args>...> ret;
input_tuple_vector_init(ret, N, std::make_index_sequence<sizeof...(Args)>());
for (int i = 0; i < N; ++i) {
input_tuple_vector_helper(ret, i, std::make_index_sequence<sizeof...(Args)>());
}
return ret;
}
} // namespace haar_lib
#line 4 "Mylib/Utils/compressor.cpp"
namespace haar_lib {
template <typename T>
class compressor {
std::vector<T> data_;
template <typename>
friend class compressor_builder;
public:
int get_index(const T &val) const {
return std::lower_bound(data_.begin(), data_.end(), val) - data_.begin();
}
auto &compress(std::vector<T> &vals) const {
for (auto &x : vals) x = get_index(x);
return *this;
}
auto &compress(T &val) const {
val = get_index(val);
return *this;
}
template <typename U, typename... Args>
auto &compress(U &val, Args &... args) const {
compress(val);
return compress(args...);
}
auto &decompress(std::vector<T> &vals) const {
for (auto &x : vals) x = data_[x];
return *this;
}
auto &decompress(T &val) const {
val = data_[val];
return *this;
}
template <typename U, typename... Args>
auto &decompress(U &val, Args &... args) const {
decompress(val);
return decompress(args...);
}
int size() const { return data_.size(); }
T operator[](int index) const { return data_[index]; }
};
template <typename T>
class compressor_builder {
std::vector<T> data_;
public:
auto &add(const T &val) {
data_.push_back(val);
return *this;
}
auto &add(const std::vector<T> &vals) {
data_.insert(data_.end(), vals.begin(), vals.end());
return *this;
}
template <typename U, typename... Args>
auto &add(const U &val, const Args &... args) {
add(val);
return add(args...);
}
auto build() const {
compressor<T> ret;
ret.data_ = data_;
std::sort(ret.data_.begin(), ret.data_.end());
ret.data_.erase(std::unique(ret.data_.begin(), ret.data_.end()), ret.data_.end());
return ret;
}
};
} // namespace haar_lib
#line 8 "test/aoj/1337/main.test.cpp"
namespace hl = haar_lib;
const int H = 200;
const int W = 200;
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
int n;
while (std::cin >> n, n) {
auto [l, t, r, b] = hl::input_tuple_vector<int, int, int, int>(n);
int64_t a[H][W] = {};
hl::compressor_builder<int>().add(l, r, -1).build().compress(l, r);
hl::compressor_builder<int>().add(t, b, -1).build().compress(t, b);
for (int i = 0; i < n; ++i) {
for (int x = l[i]; x < r[i]; ++x) {
for (int y = b[i]; y < t[i]; ++y) {
a[x][y] |= (1LL << i);
}
}
}
hl::unionfind uf(H * W);
int index[H][W];
{
int k = 0;
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
index[i][j] = k;
++k;
}
}
}
for (int i = 0; i < H; ++i) {
for (int j = 0; j < W; ++j) {
if (i + 1 < H and a[i][j] == a[i + 1][j]) uf.merge(index[i][j], index[i + 1][j]);
if (j + 1 < W and a[i][j] == a[i][j + 1]) uf.merge(index[i][j], index[i][j + 1]);
}
}
int ans = uf.count_groups();
std::cout << ans << "\n";
}
return 0;
}
Back to top page
Union-find
(Mylib/DataStructure/UnionFind/unionfind.cpp)