結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | moti |
提出日時 | 2015-11-29 20:44:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 795 ms / 4,000 ms |
コード長 | 3,350 bytes |
コンパイル時間 | 1,299 ms |
コンパイル使用メモリ | 121,620 KB |
実行使用メモリ | 192,384 KB |
最終ジャッジ日時 | 2024-05-01 16:54:52 |
合計ジャッジ時間 | 4,228 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
6,812 KB |
testcase_01 | AC | 3 ms
6,940 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 3 ms
6,944 KB |
testcase_04 | AC | 3 ms
6,940 KB |
testcase_05 | AC | 3 ms
6,940 KB |
testcase_06 | AC | 3 ms
6,940 KB |
testcase_07 | AC | 7 ms
6,944 KB |
testcase_08 | AC | 26 ms
6,940 KB |
testcase_09 | AC | 13 ms
6,944 KB |
testcase_10 | AC | 7 ms
6,944 KB |
testcase_11 | AC | 17 ms
6,940 KB |
testcase_12 | AC | 2 ms
6,944 KB |
testcase_13 | AC | 12 ms
6,940 KB |
testcase_14 | AC | 4 ms
6,940 KB |
testcase_15 | AC | 5 ms
6,940 KB |
testcase_16 | AC | 4 ms
6,940 KB |
testcase_17 | AC | 12 ms
6,944 KB |
testcase_18 | AC | 21 ms
6,940 KB |
testcase_19 | AC | 24 ms
6,940 KB |
testcase_20 | AC | 4 ms
6,940 KB |
testcase_21 | AC | 27 ms
6,940 KB |
testcase_22 | AC | 211 ms
6,944 KB |
testcase_23 | AC | 24 ms
6,940 KB |
testcase_24 | AC | 24 ms
6,944 KB |
testcase_25 | AC | 36 ms
6,944 KB |
testcase_26 | AC | 35 ms
6,944 KB |
testcase_27 | AC | 98 ms
26,112 KB |
testcase_28 | AC | 795 ms
192,384 KB |
testcase_29 | AC | 9 ms
6,940 KB |
testcase_30 | AC | 37 ms
6,940 KB |
testcase_31 | AC | 137 ms
35,456 KB |
testcase_32 | AC | 29 ms
6,940 KB |
testcase_33 | AC | 16 ms
6,944 KB |
testcase_34 | AC | 25 ms
6,940 KB |
testcase_35 | AC | 26 ms
6,944 KB |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:86:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 86 | scanf("%d%d", &H, &W); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:89:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 89 | scanf("%d", &A[i][j]); | ~~~~~^~~~~~~~~~~~~~~~ main.cpp:119:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 119 | scanf("%d", &Q); | ~~~~~^~~~~~~~~~ main.cpp:122:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 122 | scanf("%d%d%d", &r, &c, &x); r--, c--; | ~~~~~^~~~~~~~~~~~~~~~~~~~~~
ソースコード
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <complex> #include <queue> #include <deque> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <iomanip> #include <assert.h> #include <array> #include <cstdio> #include <cstring> #include <random> #include <functional> #include <numeric> #include <bitset> using namespace std; #define REP(i,a,b) for(int i=a;i<(int)b;i++) #define rep(i,n) REP(i,0,n) #define all(c) (c).begin(), (c).end() #define minus(c) memset(c, -1, sizeof c) struct UnionFind { // vector<int> rank; // vector<int> rid; int rank[200*200+1]; int rid[200*200+1]; UnionFind(int n) { rep(i, n) rid[i] = -1; } void unite(int u, int v) { u = root(u), v = root(v); if(u == v) { return ; } if(rank[u] < rank[v]) { rid[u] = v; } else { rid[v] = u; if(rank[u] == rank[v]) { rank[u]++; } } } bool same(int u, int v) { return root(u) == root(v); } inline int root(int x) { if(rid[x] < 0) return x; else return rid[x] = root(rid[x]); } inline int operator[](int x) { return root(x); } }; int dx[4] = {-1,0,1,0}; int dy[4] = {0,-1,0,1}; int H, W; int A[201][201]; int Q; bool rootCol[200*200+1]; vector<int> outers[200*200+1]; // []はroot bool inrange(int y, int x) { return 0<=y&&y<H && 0<=x&&x<W; } typedef pair<int, int> pii; inline int chpos(int y, int x) { return y*W+x; } inline pii coord(int p) { return std::move(make_pair(p/W, p%W)); } int main() { scanf("%d%d", &H, &W); rep(i, H) rep(j, W) { scanf("%d", &A[i][j]); rootCol[chpos(i, j)] = A[i][j]; } UnionFind uf(H * W + 1); rep(i, H) rep(j, W) rep(k, 4) { int ni = i+dy[k], nj = j+dx[k]; if(!inrange(ni, nj)) { continue; } if(A[i][j] == A[ni][nj]) { uf.unite(chpos(i, j), chpos(ni, nj)); rootCol[uf.root(chpos(i, j))] = A[i][j]; } } rep(i, H) rep(j, W) rep(k, 4) { int ni = i+dy[k], nj = j+dx[k]; if(!inrange(ni, nj)) { continue; } if(A[i][j] != A[ni][nj]) { outers[uf[chpos(i, j)]].push_back(uf[chpos(ni, nj)]); } } rep(i, H) rep(j, W) { int rt = uf[chpos(i, j)]; if(outers[rt].empty()) { continue; } stable_sort(all(outers[rt])); outers[rt].erase(unique(all(outers[rt])), outers[rt].end()); } scanf("%d", &Q); rep(_, Q) { int r, c, x; scanf("%d%d%d", &r, &c, &x); r--, c--; int const RawPos = uf[chpos(r, c)]; if(rootCol[RawPos] != x) { int size = outers[RawPos].size(); rep(i, size) { auto e = outers[RawPos][i]; if(uf.same(e, RawPos)) { outers[RawPos].erase(outers[RawPos].begin() + i); i--; size--; continue; } if(rootCol[uf[e]] != rootCol[RawPos]) { copy(all(outers[uf[e]]), back_inserter(outers[RawPos])); size = outers[RawPos].size(); uf.unite(e, RawPos); } } int rt = uf.root(RawPos); if(RawPos != rt) { swap(outers[rt], outers[RawPos]); } stable_sort(all(outers[rt])); outers[rt].erase(unique(all(outers[rt])), outers[rt].end()); rootCol[rt] = x; } } rep(i, H) { rep(j, W) { if(j) printf(" "); printf("%d", rootCol[uf.root(chpos(i, j))]); } puts(""); } return 0; }