結果

問題 No.13 囲みたい！
コンテスト
ユーザー commy
提出日時 2018-08-12 21:33:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 4 ms / 5,000 ms
コード長 1,728 bytes
コンパイル時間 778 ms
コンパイル使用メモリ 78,148 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-24 07:33:54
合計ジャッジ時間 1,517 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 16
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
#define dump(val) cerr << __LINE__ << ":\t" << #val << " = " << (val) << endl

using namespace std;

typedef long long int lli;

template<typename T>
vector<T> make_v(size_t a, T b) {
    return vector<T>(a, b);
}

template<typename... Ts>
auto make_v(size_t a, Ts... ts) {
    return vector<decltype(make_v(ts...))>(a, make_v(ts...));
}

class UnionFind {
private:
    vector<int> par;

public:
    UnionFind(int n) {
        par.resize(n);
        REP(i, 0, n) {
            par[i] = i;
        }
    }
    int Find(int n) {
        return (par[n] == n ? n : par[n] = Find(par[n]));
    }
    bool Union(int a, int b) {
        a = Find(a);
        b = Find(b);
        if (a == b) return false;
        par[a] = b;
        return true;
    }
    bool Same(int a, int b) {
        return (Find(a) == Find(b));
    }
};

int main() {
    int W, H;
    cin >> W >> H;
    auto M = make_v(H + 2, W + 2, 0);
    REP(i, 1, H + 1) {
        REP(j, 1, W + 1) {
            cin >> M[i][j];
        }
    }
    UnionFind uf((H + 2) * (W + 2));
    const int dx[2] = {0, 1};
    const int dy[2] = {1, 0};
    bool ok = false;
    REP(i, 1, H + 1) {
        REP(j, 1, W + 1) {
            int bs = (W + 2) * i + j;
            REP(k, 0, 2) {
                int nx = j + dx[k];
                int ny = i + dy[k];
                int nb = (W + 2) * ny + nx;
                if (M[i][j] != M[ny][nx]) continue;
                if (!uf.Union(bs, nb)) {
                    ok = true;
                }
            }
        }
    }
    cout << (ok ? "possible" : "impossible") << endl;
    return 0;
}
0