#940127 (C++23) No.697 池の数はいくつか

提出ソース

結果

問題	No.697 池の数はいくつか
ユーザー	kobaryo222
提出日時	2023-12-24 14:25:27
言語	C++23 (gcc 12.3.0 + boost 1.83.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

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,940 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	2 ms 6,944 KB
testcase_05	AC	2 ms 6,944 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	2 ms 6,944 KB
testcase_13	AC	2 ms 6,944 KB
testcase_14	AC	2 ms 6,940 KB
testcase_15	AC	2 ms 6,940 KB
testcase_16	AC	2 ms 6,944 KB
testcase_17	AC	2 ms 6,940 KB
testcase_18	AC	2 ms 6,940 KB
testcase_19	AC	2 ms 6,944 KB
testcase_20	AC	2 ms 6,944 KB
testcase_21	AC	2 ms 6,944 KB
testcase_22	AC	2 ms 6,940 KB
testcase_23	AC	2 ms 6,940 KB
testcase_24	AC	201 ms 12,316 KB
testcase_25	AC	202 ms 12,184 KB
testcase_26	AC	203 ms 12,308 KB
testcase_27	AC	203 ms 12,312 KB
testcase_28	AC	200 ms 12,308 KB
testcase_29	AC	1,545 ms 73,496 KB
testcase_30	AC	1,831 ms 82,660 KB
testcase_31	AC	1,519 ms 73,628 KB
testcase_32	AC	1,800 ms 83,368 KB
testcase_33	AC	1,791 ms 83,308 KB
testcase_34	AC	1,798 ms 82,496 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#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;
}