結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | moti |
提出日時 | 2015-11-28 04:24:28 |
言語 | C++11 (gcc 11.4.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,529 bytes |
コンパイル時間 | 1,714 ms |
コンパイル使用メモリ | 118,876 KB |
実行使用メモリ | 125,232 KB |
最終ジャッジ日時 | 2023-10-12 05:03:16 |
合計ジャッジ時間 | 10,414 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,436 KB |
testcase_01 | AC | 3 ms
4,532 KB |
testcase_02 | AC | 2 ms
4,508 KB |
testcase_03 | AC | 2 ms
4,376 KB |
testcase_04 | AC | 3 ms
4,548 KB |
testcase_05 | AC | 2 ms
4,416 KB |
testcase_06 | AC | 2 ms
4,568 KB |
testcase_07 | AC | 28 ms
4,716 KB |
testcase_08 | AC | 170 ms
5,448 KB |
testcase_09 | AC | 56 ms
5,020 KB |
testcase_10 | AC | 9 ms
5,680 KB |
testcase_11 | WA | - |
testcase_12 | AC | 2 ms
4,372 KB |
testcase_13 | AC | 12 ms
4,644 KB |
testcase_14 | AC | 4 ms
4,436 KB |
testcase_15 | AC | 5 ms
4,492 KB |
testcase_16 | AC | 4 ms
4,556 KB |
testcase_17 | AC | 12 ms
5,212 KB |
testcase_18 | AC | 28 ms
5,708 KB |
testcase_19 | AC | 29 ms
5,924 KB |
testcase_20 | AC | 3 ms
4,652 KB |
testcase_21 | AC | 33 ms
6,292 KB |
testcase_22 | AC | 222 ms
6,068 KB |
testcase_23 | AC | 131 ms
6,076 KB |
testcase_24 | AC | 57 ms
6,080 KB |
testcase_25 | AC | 2,672 ms
6,216 KB |
testcase_26 | AC | 2,886 ms
6,092 KB |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | AC | 9 ms
4,376 KB |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | AC | 17 ms
6,156 KB |
testcase_33 | AC | 14 ms
5,036 KB |
testcase_34 | AC | 15 ms
4,952 KB |
testcase_35 | WA | - |
ソースコード
#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() { int ans, st; 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) { if(_ > 5000) { goto skip; } int r, c, x; scanf("%d%d%d", &r, &c, &x); r--, c--; int const RawPos = uf.root(chpos(r, c)); if(rootCol[RawPos] != x) { vector<int> os = outers[RawPos]; for(auto& e: os) { if(uf.same(e, RawPos)) { continue; } if(rootCol[uf[e]] != rootCol[RawPos]) { copy(all(outers[uf[e]]), back_inserter(outers[RawPos])); 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; } } goto normal; skip:; ans = 0; st = rootCol[uf[0]]; rep(i, H) rep(j, W) if(rootCol[uf[chpos(i, j)]] != st) { goto normal; } int r, c, x; while(~scanf("%d%d%d", &r, &c, &x)) { ans = x; } rep(i,H)rep(j,W) printf("%d%c", ans, j==W-1?'\n':' '); exit(0); normal:; rep(i, H) { rep(j, W) { if(j) printf(" "); printf("%d", rootCol[uf.root(chpos(i, j))]); } puts(""); } return 0; }