結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー |
![]() |
提出日時 | 2015-11-28 10:52:11 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 56 ms / 4,000 ms |
コード長 | 3,574 bytes |
コンパイル時間 | 1,085 ms |
コンパイル使用メモリ | 111,284 KB |
実行使用メモリ | 16,584 KB |
最終ジャッジ日時 | 2024-11-21 22:01:16 |
合計ジャッジ時間 | 3,066 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 36 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:110:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 110 | scanf("%d", &k[i][j]); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:141:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 141 | scanf("%d", &q); | ~~~~~^~~~~~~~~~ main.cpp:145:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 145 | scanf("%d%d", &a, &b); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:149:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 149 | scanf("%d", &x); | ~~~~~^~~~~~~~~~
ソースコード
#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cctype>#include<cstdlib>#include<algorithm>#include<bitset>#include<vector>#include<list>#include<deque>#include<queue>#include<map>#include<set>#include<stack>#include<cmath>#include<sstream>#include<fstream>#include<iomanip>#include<ctime>#include<complex>#include<functional>#include<climits>#include<cassert>#include<iterator>#include<unordered_map>#include<unordered_set>using namespace std;#define MAX 212pair<int, int> co[MAX*MAX];int cnt[MAX][MAX];int recently[MAX*MAX];int belong[MAX*MAX];unordered_set<int> mp[MAX*MAX];int cl[MAX*MAX];inline int root(int b) {if (belong[b] == -1) {return b;}belong[b] = root(belong[b]);return belong[b];}void merge(int a, int b) {a = root(a);b = root(b);if (a == b) {return;}if (recently[a] > recently[b]) {}else {swap(a, b);}if (mp[a].size() < mp[b].size()) {swap(mp[a], mp[b]);}for (auto ite = mp[b].begin();ite != mp[b].end();ite++) {if (cl[root(*ite)] != cl[b]) {mp[a].insert(root(*ite));}}mp[b].clear();belong[b] = a;}int k[MAX][MAX];int h;int w;int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 };unordered_set<int> cp;int ope = 0;int want;void change(int b) {cl[b] = want;recently[b] = ope;bool update = true;while (update) {update = false;cp.clear();vector<pair<int, int> > V;V.clear();for (auto ite = mp[b].begin();ite != mp[b].end();ite++) {if (root(*ite)!=b&&cl[root((*ite))] == cl[b]) {V.push_back(make_pair(root((*ite)), b));}else {cp.insert((root(*ite)));}}swap(mp[b], cp);for (int i = 0;i < V.size();i++) {update = true;merge(V[i].first, V[i].second);}update = false;}}int main() {cin >> h >> w;int C = 0;for (int i = 0;i < h;i++) {for (int j = 0;j < w;j++) {scanf("%d", &k[i][j]);if (k[i][j]>1) {exit(1);}if (k[i][j] < 0) {exit(1);}cnt[i][j] = C;C++;//co[C - 1] = make_pair(i, j);cl[C - 1] = k[i][j];}}memset(belong, -1, sizeof(belong));for (int i = 0;i < h;i++) {for (int j = 0;j < w;j++) {for (int k1 = 0;k1 < 4;k1++) {int ii = i + dx[k1];int jj = j + dy[k1];if (ii >= 0 && jj >= 0 && ii < h&&jj < w&&k[i][j] == k[ii][jj]) {merge(cnt[ii][jj], cnt[i][j]);}else {if(ii>=0&&jj>=0&&ii<h&&jj<w){mp[root(cnt[i][j])].insert(root(cnt[ii][jj]));}}}}}int q;scanf("%d", &q);while (q--) {ope++;int a, b;scanf("%d%d", &a, &b);a--;b--;int x;scanf("%d", &x);int f = root(cnt[a][b]);if (cl[f] == x) {continue;}want = x;change(f);}for (int i = 0;i < h;i++) {for (int j = 0;j < w;j++) {int f = cl[root(cnt[i][j])];if (j) {printf(" ");}printf("%d", f);}puts("");}return 0;}