結果

問題 No.307 最近色塗る問題多くない？
ユーザー kimiyukikimiyuki
提出日時 2016-03-01 22:19:57
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,330 bytes
コンパイル時間 1,032 ms
コンパイル使用メモリ 84,004 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-09-24 13:14:20
合計ジャッジ時間 8,869 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 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,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 8 ms
6,940 KB
testcase_08 AC 31 ms
6,940 KB
testcase_09 AC 13 ms
6,944 KB
testcase_10 AC 13 ms
6,944 KB
testcase_11 AC 64 ms
6,944 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 25 ms
6,940 KB
testcase_14 AC 4 ms
6,944 KB
testcase_15 AC 4 ms
6,940 KB
testcase_16 AC 4 ms
6,944 KB
testcase_17 AC 14 ms
6,944 KB
testcase_18 AC 33 ms
8,832 KB
testcase_19 AC 37 ms
10,240 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 49 ms
14,464 KB
testcase_22 AC 57 ms
13,952 KB
testcase_23 AC 51 ms
14,208 KB
testcase_24 AC 54 ms
14,336 KB
testcase_25 AC 81 ms
13,952 KB
testcase_26 AC 83 ms
14,464 KB
testcase_27 AC 905 ms
15,104 KB
testcase_28 TLE -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <unordered_set>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
typedef long long ll;
using namespace std;
struct union_find {
    vector<int> tree;
    explicit union_find(size_t n) : tree(n, -1) {}
    bool is_root(int a) { return tree[a] < 0; }
    int find_root(int a) { return is_root(a) ? a : (tree[a] = find_root(tree[a])); }
    int tree_size(int a) { return - tree[find_root(a)]; }
    void union_tree(int a, int b) {
        a = find_root(a); b = find_root(b);
        if (a != b) {
            if (not (tree_size(a) < tree_size(b))) swap(a,b);
            tree[b] += tree[a];
            tree[a] = b;
        }
    }
    bool is_connected(int a, int b) { return find_root(a) == find_root(b); }
};
int main() {
    int h, w; cin >> h >> w;
    auto ix = [&](int y, int x) { return y*w + x; };
    vector<int> a(h * w); repeat (y,h) repeat (x,w) cin >> a[ix(y,x)];
    union_find t(h * w);
    repeat (y,h) repeat (x,w) {
        if (y+1 < h and a[ix(y,x)] == a[ix(y+1,x)]) t.union_tree(ix(y,x), ix(y+1,x));
        if (x+1 < w and a[ix(y,x)] == a[ix(y,x+1)]) t.union_tree(ix(y,x), ix(y,x+1));
    }
    auto root = [&](int y, int x) { return t.find_root(ix(y,x)); };
    vector<unordered_set<int> > g(h * w);
    repeat (y,h) repeat (x,w) {
        if (y+1 < h and a[ix(y,x)] != a[ix(y+1,x)]) {
            g[root(y,x)].insert(root(y+1,x));
            g[root(y+1,x)].insert(root(y,x));
        }
        if (x+1 < w and a[ix(y,x)] != a[ix(y,x+1)]) {
            g[root(y,x)].insert(root(y,x+1));
            g[root(y,x+1)].insert(root(y,x));
        }
    }
    int q; cin >> q;
    repeat (query,q) {
        int y, x, p; cin >> y >> x >> p; -- y; -- x;
        int i = root(y,x);
        if (a[i] == p) continue;
        a[i] = p;
        for (int j : g[i]) t.union_tree(i,j);
        int l = t.find_root(i);
        unordered_set<int> s;
        for (int j : g[i]) {
            for (int k : g[j]) if (k != i) {
                g[k].erase(i);
                g[k].erase(j);
                g[k].insert(l);
                s.insert(k);
            }
        }
        g[l] = s;
        a[l] = p;
    }
    repeat (y,h) {
        repeat (x,w) {
            if (x) cout << ' ';
            cout << a[root(y,x)];
        }
        cout << endl;
    }
    return 0;
}
0