結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | k |
提出日時 | 2021-04-25 16:25:50 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,983 ms / 4,000 ms |
コード長 | 2,752 bytes |
コンパイル時間 | 2,436 ms |
コンパイル使用メモリ | 217,800 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-04 09:30:00 |
合計ジャッジ時間 | 11,081 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 3 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 2 ms
5,376 KB |
testcase_07 | AC | 6 ms
5,376 KB |
testcase_08 | AC | 34 ms
5,376 KB |
testcase_09 | AC | 12 ms
5,376 KB |
testcase_10 | AC | 12 ms
5,376 KB |
testcase_11 | AC | 55 ms
5,376 KB |
testcase_12 | AC | 2 ms
5,376 KB |
testcase_13 | AC | 11 ms
5,376 KB |
testcase_14 | AC | 3 ms
5,376 KB |
testcase_15 | AC | 4 ms
5,376 KB |
testcase_16 | AC | 3 ms
5,376 KB |
testcase_17 | AC | 16 ms
5,376 KB |
testcase_18 | AC | 45 ms
5,376 KB |
testcase_19 | AC | 44 ms
5,376 KB |
testcase_20 | AC | 3 ms
5,376 KB |
testcase_21 | AC | 41 ms
5,376 KB |
testcase_22 | AC | 27 ms
5,376 KB |
testcase_23 | AC | 164 ms
5,376 KB |
testcase_24 | AC | 90 ms
5,376 KB |
testcase_25 | AC | 119 ms
5,376 KB |
testcase_26 | AC | 180 ms
5,376 KB |
testcase_27 | AC | 1,980 ms
5,376 KB |
testcase_28 | AC | 1,669 ms
5,376 KB |
testcase_29 | AC | 8 ms
5,376 KB |
testcase_30 | AC | 185 ms
5,376 KB |
testcase_31 | AC | 1,983 ms
5,376 KB |
testcase_32 | AC | 19 ms
5,376 KB |
testcase_33 | AC | 14 ms
5,376 KB |
testcase_34 | AC | 19 ms
5,376 KB |
testcase_35 | AC | 24 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; class union_find { int n; int cnt; // number of connected components vector<int> par; vector<int> rank; vector<int> sz; // size of each component public: union_find(int n) : n(n), cnt(n), par(n), rank(n), sz(n) { for (int i = 0; i < n; i++) { par[i] = i; sz[i] = 1; } } int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; --cnt; if (rank[x] < rank[y]) { par[x] = y; sz[y] += sz[x]; } else { par[y] = x; sz[x] += sz[y]; if (rank[x] == rank[y]) ++rank[x]; } } bool same(int x, int y) { return find(x) == find(y); } int compCnt() { return cnt; } int size(int x) { return sz[find(x)]; } }; int dy[] = {0, 1, 0, -1}; int dx[] = {1, 0, -1, 0}; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int r, c; cin >> r >> c; vector<vector<int> > bd(r, vector<int>(c)); for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) cin >> bd[i][j]; union_find tree(r * c); for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { for (int k = 0; k < 4; k++) { int it = i + dy[k]; int jt = j + dx[k]; if (0 <= it && it < r && 0 <= jt && jt < c) { if (bd[i][j] == bd[it][jt]) { tree.unite(i * c + j, it * c + jt); } } } } } int q; cin >> q; vector<int> xs(q), ys(q), zs(q); for (int t = 0; t < q; t++) cin >> ys[t] >> xs[t] >> zs[t]; for (int t = 0; t < q; t++) { int y = ys[t] - 1; int x = xs[t] - 1; int z = zs[t]; int root = tree.find(y * c + x); if (bd[root/c][root%c] == z) continue; set<int> added; for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (!tree.same(root, i * c + j)) continue; for (int k = 0; k < 4; k++) { int it = i + dy[k]; int jt = j + dx[k]; if (0 <= it && it < r && 0 <= jt && jt < c) { if (!tree.same(root, it * c + jt)) { added.insert(it * c + jt); } } } } } for (int a: added) tree.unite(root, a); root = tree.find(root); bd[root/c][root%c] = z; if (tree.compCnt() == 1) break; } if (tree.compCnt() == 1) { int root = tree.find(0); bd[root/c][root%c] = zs.back(); } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { int root = tree.find(i * c + j); cout << bd[root/c][root%c] << " "; } cout << endl; } return 0; }