結果

問題 No.697 池の数はいくつか
ユーザー kobaryo222
提出日時 2023-12-24 14:25:27
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,831 ms / 6,000 ms
コード長 6,002 bytes
コンパイル時間 3,744 ms
コンパイル使用メモリ 258,008 KB
実行使用メモリ 83,368 KB
最終ジャッジ日時 2024-09-27 13:43:43
合計ジャッジ時間 18,639 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "src/test/verify/yuki-697.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/697"
#line 2 "src/template.hpp"

/**
 * @brief テンプレート
 * @docs docs/template.md
 */

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using pl = pair<ll, ll>;
using vp = vector<pl>;
using vvp = vector<vp>;
using vs = vector<string>;
using vvs = vector<vs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vd = vector<double>;
using vvd = vector<vd>;
using vvvd = vector<vvd>;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for(ll i = ll(a); i < ll(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define all(x) std::begin(x), std::end(x)
#define make_unique(v) v.erase(unique(all(v)), v.end());
#define sum(...) accumulate(all(__VA_ARGS__), 0LL)

constexpr ll inf = 0x1fffffffffffffffLL;

template <class T1, class T2> void input(vector<T1> &v1, vector<T2> &v2){ rep(i, v1.size()) cin >> v1[i] >> v2[i]; }
template <class T1, class T2, class T3> void input(vector<T1> &v1, vector<T2> &v2, vector<T3> &v3) { rep(i, v1.size()) cin >> v1[i] >> v2[i] >> v3[i]; }
template <class T1, class T2, class T3, class T4> void input(vector<T1> &v1, vector<T2> &v2, vector<T3> &v3, vector<T4> &v4) { rep(i, v1.size()) cin >> v1[i] >> v2[i] >> v3[i] >> v4[i]; }

template <class T> istream &operator>>(istream &is, vector<T> &v) {
    for(auto &x : v) {
        is >> x;
    }
    return is;
}

template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for(int i = 0; i < (int)v.size(); i++) {
        if(i != (int)v.size() - 1)
            os << v[i] << " ";
        else
            os << v[i];
    }
    return os;
}

template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
    is >> p.first >> p.second;
    return is;
}

template <class T, class U>
ostream &operator<<(ostream &os, pair<T, U> &p) {
    os << p.first << " " << p.second;
    return os;
}

template <typename T, typename... Args>
auto vec(T x, int arg, Args... args) {
    if constexpr(sizeof...(args) == 0)
        return vector<T>(arg, x);
    else
        return vector(arg, vec<T>(x, args...));
}

template <class T> auto min(const T &a) { return *min_element(all(a)); }
template <class T> auto max(const T &a) { return *max_element(all(a)); }
template <class T> bool chmin(T &a, const T &b) { return a > b ? a = b, true : false; }
template <class T> bool chmax(T &a, const T &b) { return a < b ? a = b, true : false; }

constexpr ll bit(ll x){ return 1LL << x; }
constexpr ll msk(ll x){ return (1LL << x) - 1;}
constexpr bool stand(ll x, int i) { return x & bit(i); }

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;
#line 2 "src/Util/grid2d.hpp"

/**
 * @brief Grid(2D)
 * @docs docs/grid2d.md
 */

template <typename T>
struct Grid2D{
    int H, W;
    vector<vector<T>> data;
    vector<int> dx = {1, -1, 0, 0, 1, -1, 1, -1};
    vector<int> dy = {0, 0, 1, -1, 1, -1, -1, 1};
    Grid2D(int H, int W) : H(H), W(W), data(H, vector<T>(W)) {}
    Grid2D(int H, int W, T x) : H(H), W(W), data(H, vector<T>(W, x)) {}
    Grid2D(const vector<vector<T>> &data) : H(data.size()), W(data[0].size()), data(data) {}
    vector<T> &operator[](int i){
        return data[i];
    }
    void read(){
        for(int i = 0; i < H; i++){
            for(int j = 0; j < W; j++){
                cin >> data[i][j];
            }
        }
    }
    bool in(int i, int j){
        return 0 <= i && i < H && 0 <= j && j < W;
    }
    int encode(int i, int j){
        return i * W + j;
    }
    pair<int, int> decode(int x){
        return make_pair(x / W, x % W);
    }
    vector<pair<int, int>> next4(int i, int j){
        return next(i, j, 4);
    }
    vector<pair<int, int>> next8(int i, int j){
        return next(i, j, 8);
    }
private:
    vector<pair<int, int>> next(int i, int j, int k){
        vector<pair<int, int>> res;
        for(int t = 0; t < k; t++){
            int ni = i + dx[t], nj = j + dy[t];
            if(in(ni, nj)) res.push_back(make_pair(ni, nj));
        }
        return res;
    }
};
#line 2 "src/DataStructure/union-find.hpp"

/**
 * @brief Union-Find
 * @docs docs/union-find.md
 */

struct UnionFind {
    vector<int> par;
    UnionFind(int n) {
        par.assign(n, -1);
    };
    int root(int x) {
        if(par[x] < 0)
            return x;
        else
            return par[x] = root(par[x]);
    }
    int size(int x) {
        x = root(x);
        return -1 * par[x];
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if(x == y)
            return false;
        if(size(x) < size(y))
            swap(x, y);
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    vector<int> leaders(){
        vector<int> res;
        for(int i = 0; i < (int)par.size(); i++){
            if(par[i] < 0)
                res.push_back(i);
        }
        return res;
    }
};
#line 5 "src/test/verify/yuki-697.test.cpp"

int main(){
    ll H, W;
    cin >> H >> W;
    Grid2D<int> grid(H, W);
    grid.read();
    UnionFind uf(H * W);
    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
            for(auto [ni, nj] : grid.next4(i, j)){
                if(grid[i][j] == grid[ni][nj]){
                    uf.unite(grid.encode(i, j), grid.encode(ni, nj));
                }
            }
        }
    }
    ll ans = 0;
    for(auto i : uf.leaders()){
        auto [nx, ny] = grid.decode(i);
        if(grid[nx][ny] == 1) ans++;
    }
    cout << ans << endl;
}
0