結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | firiexp |
提出日時 | 2019-11-27 19:00:30 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,243 bytes |
コンパイル時間 | 830 ms |
コンパイル使用メモリ | 92,600 KB |
最終ジャッジ日時 | 2024-11-14 21:53:43 |
合計ジャッジ時間 | 1,596 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
main.cpp: In function 'int main()': main.cpp:59:19: error: variable 'std::array<int, 4> dx' has initializer but incomplete type 59 | array<int, 4> dx{-1, 1, 0, 0}, dy{0, 0, -1, 1}; | ^~ main.cpp:59:36: error: variable 'std::array<int, 4> dy' has initializer but incomplete type 59 | array<int, 4> dx{-1, 1, 0, 0}, dy{0, 0, -1, 1}; | ^~
ソースコード
#include <limits> #include <iostream> #include <algorithm> #include <iomanip> #include <map> #include <set> #include <queue> #include <stack> #include <numeric> #include <bitset> #include <cmath> static const int MOD = 1000000007; using ll = long long; using namespace std; template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208; class UnionFind { int n; vector<int> uni; int forest_size; public: explicit UnionFind(int n) : n(n), uni(static_cast<size_t>(n), -1), forest_size(n) {}; int root(int a){ if (uni[a] < 0) return a; else return (uni[a] = root(uni[a])); } bool unite(int a, int b) { a = root(a); b = root(b); if(a == b) return false; if(uni[a] > uni[b]) swap(a, b); uni[a] += uni[b]; uni[b] = a; forest_size--; return true; } int size(){ return forest_size; } int size(int i){ return -uni[root(i)]; } bool same(int a, int b) { return root(a) == root(b); } }; int main() { int h, w; cin >> h >> w; vector<vector<int>> v(h+2, vector<int>(w+2, -1)); vector<int> val(h*w); for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { cin >> v[i+1][j+1]; val[i*w+j] = v[i+1][j+1]; } } UnionFind uf(h*w); vector<vector<int>> G(h*w); array<int, 4> dx{-1, 1, 0, 0}, dy{0, 0, -1, 1}; auto f = [&](int i, int j){ return i*w+j; }; for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { for (int k = 0; k < 4; ++k) { if(v[i+1+dy[k]][j+1+dx[k]] < 0) continue; if(v[i+1+dy[k]][j+1+dx[k]] == v[i+1][j+1]) { uf.unite(f(i, j), f(i+dy[k], j+dx[k])); } } } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { for (int k = 0; k < 4; ++k) { if(v[i+1+dy[k]][j+1+dx[k]] < 0) continue; if(v[i+1+dy[k]][j+1+dx[k]] != v[i+1][j+1]) { G[uf.root(f(i, j))].emplace_back(uf.root(f(i+dy[k], j+dx[k]))); G[uf.root(f(i, j))].emplace_back(uf.root(f(i+dy[k], j+dx[k]))); } } } } for (int i = 0; i < h*w; ++i) { sort(G[i].begin(), G[i].end()); G[i].erase(unique(G[i].begin(), G[i].end()), G[i].end()); } int q; cin >> q; for (int i = 0; i < q; ++i) { int a, b, c; scanf("%d %d %d", &a, &b, &c); a--; b--; int x = uf.root(f(a, b)); if(val[x] == c) continue; vector<int> p; for (auto &&j : G[x]) { for (auto &&k : G[uf.root(j)]) { if(uf.root(k) != x) p.emplace_back(uf.root(k)); } G[uf.root(j)].clear(); } for (auto &&j : G[x]) { uf.unite(j, x); } sort(p.begin(), p.end()); p.erase(unique(p.begin(), p.end()), p.end()); val[uf.root(x)] = c; G[uf.root(x)] = p; } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if(j) printf(" "); printf("%d", val[uf.root(f(i, j))]); } puts(""); } return 0; }