結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | Kmcode1 |
提出日時 | 2015-11-28 10:52:11 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 69 ms / 4,000 ms |
コード長 | 3,574 bytes |
コンパイル時間 | 1,196 ms |
コンパイル使用メモリ | 113,236 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-05-01 16:46:38 |
合計ジャッジ時間 | 3,375 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,272 KB |
testcase_01 | AC | 3 ms
6,016 KB |
testcase_02 | AC | 4 ms
6,272 KB |
testcase_03 | AC | 4 ms
6,144 KB |
testcase_04 | AC | 4 ms
6,400 KB |
testcase_05 | AC | 3 ms
6,144 KB |
testcase_06 | AC | 4 ms
6,144 KB |
testcase_07 | AC | 8 ms
6,912 KB |
testcase_08 | AC | 30 ms
8,704 KB |
testcase_09 | AC | 14 ms
7,296 KB |
testcase_10 | AC | 8 ms
6,912 KB |
testcase_11 | AC | 15 ms
7,296 KB |
testcase_12 | AC | 3 ms
6,272 KB |
testcase_13 | AC | 17 ms
6,272 KB |
testcase_14 | AC | 6 ms
6,528 KB |
testcase_15 | AC | 6 ms
6,656 KB |
testcase_16 | AC | 5 ms
6,784 KB |
testcase_17 | AC | 15 ms
8,192 KB |
testcase_18 | AC | 31 ms
11,136 KB |
testcase_19 | AC | 36 ms
11,972 KB |
testcase_20 | AC | 5 ms
6,656 KB |
testcase_21 | AC | 46 ms
16,000 KB |
testcase_22 | AC | 53 ms
15,232 KB |
testcase_23 | AC | 50 ms
15,872 KB |
testcase_24 | AC | 50 ms
16,128 KB |
testcase_25 | AC | 65 ms
15,744 KB |
testcase_26 | AC | 65 ms
16,256 KB |
testcase_27 | AC | 50 ms
16,256 KB |
testcase_28 | AC | 69 ms
16,440 KB |
testcase_29 | AC | 12 ms
6,144 KB |
testcase_30 | AC | 66 ms
16,512 KB |
testcase_31 | AC | 57 ms
16,384 KB |
testcase_32 | AC | 43 ms
16,128 KB |
testcase_33 | AC | 17 ms
7,424 KB |
testcase_34 | AC | 29 ms
7,424 KB |
testcase_35 | AC | 28 ms
7,296 KB |
コンパイルメッセージ
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 212 pair<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; }