結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | is_eri23 |
提出日時 | 2015-11-28 20:53:52 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 81 ms / 4,000 ms |
コード長 | 5,466 bytes |
コンパイル時間 | 1,992 ms |
コンパイル使用メモリ | 176,296 KB |
実行使用メモリ | 13,488 KB |
最終ジャッジ日時 | 2024-05-01 16:52:10 |
合計ジャッジ時間 | 3,978 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 3 ms
5,632 KB |
testcase_01 | AC | 3 ms
5,632 KB |
testcase_02 | AC | 3 ms
5,632 KB |
testcase_03 | AC | 4 ms
5,632 KB |
testcase_04 | AC | 4 ms
5,760 KB |
testcase_05 | AC | 3 ms
5,632 KB |
testcase_06 | AC | 4 ms
5,632 KB |
testcase_07 | AC | 8 ms
6,144 KB |
testcase_08 | AC | 33 ms
7,424 KB |
testcase_09 | AC | 16 ms
6,656 KB |
testcase_10 | AC | 8 ms
5,888 KB |
testcase_11 | AC | 14 ms
6,400 KB |
testcase_12 | AC | 4 ms
5,632 KB |
testcase_13 | AC | 15 ms
5,760 KB |
testcase_14 | AC | 6 ms
5,760 KB |
testcase_15 | AC | 7 ms
5,888 KB |
testcase_16 | AC | 6 ms
5,888 KB |
testcase_17 | AC | 17 ms
7,040 KB |
testcase_18 | AC | 35 ms
9,344 KB |
testcase_19 | AC | 39 ms
10,112 KB |
testcase_20 | AC | 5 ms
5,888 KB |
testcase_21 | AC | 46 ms
12,928 KB |
testcase_22 | AC | 55 ms
12,416 KB |
testcase_23 | AC | 50 ms
12,928 KB |
testcase_24 | AC | 54 ms
13,056 KB |
testcase_25 | AC | 67 ms
12,672 KB |
testcase_26 | AC | 70 ms
13,184 KB |
testcase_27 | AC | 46 ms
13,312 KB |
testcase_28 | AC | 81 ms
13,488 KB |
testcase_29 | AC | 12 ms
5,632 KB |
testcase_30 | AC | 63 ms
13,312 KB |
testcase_31 | AC | 50 ms
13,312 KB |
testcase_32 | AC | 33 ms
13,312 KB |
testcase_33 | AC | 17 ms
6,656 KB |
testcase_34 | AC | 26 ms
6,784 KB |
testcase_35 | AC | 27 ms
6,912 KB |
ソースコード
#include <bits/stdc++.h> #define EPS 1e-9 #define INF 1070000000LL #define MOD 1000000007LL #define fir first #define foreach(it,X) for(auto it=(X).begin();it!=(X).end();it++) #define numa(x,a) for(auto x: a) #define ite iterator #define mp make_pair #define rep(i,n) rep2(i,0,n) #define rep2(i,m,n) for(int i=m;i<(n);i++) #define pb push_back #define pf push_front #define sec second #define sz(x) ((int)(x).size()) #define ALL( c ) (c).begin(), (c).end() #define gcd(a,b) __gcd(a,b) #define mem(x,n) memset(x,n,sizeof(x)) #define endl "\n" using namespace std; template <int POS, class TUPLE> void deploy(std::ostream &os, const TUPLE &tuple){} template <int POS, class TUPLE, class H, class ...Ts> void deploy(std::ostream &os, const TUPLE &t){ os << (POS == 0 ? "" : ", ") << get<POS>(t); deploy<POS + 1, TUPLE, Ts...>(os, t); } template <class T,class U> std::ostream& operator<<(std::ostream &os, std::pair<T,U> &p){ os << "(" << p.first <<", " << p.second <<")";return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::vector<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "}" : ", "); return os; } template <class T> std::ostream& operator<<(std::ostream &os, std::set<T> &v){ int remain = v.size(); os << "{"; for(auto e: v) os << e << (--remain == 0 ? "}" : ", "); return os; } template <class T, class K> std::ostream& operator<<(std::ostream &os, std::map<T, K> &mp){ int remain = mp.size(); os << "{"; for(auto e: mp) os << "(" << e.first << " -> " << e.second << ")" << (--remain == 0 ? "}" : ", "); return os; } #define DEBUG1(var0) { std::cerr << (#var0) << "=" << (var0) << endl; } #define DEBUG2(var0, var1) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG1(var1); } #define DEBUG3(var0, var1, var2) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG2(var1,var2); } #define DEBUG4(var0, var1, var2, var3) { std::cerr << (#var0) << "=" << (var0) << ", ";DEBUG3(var1,var2,var3); } using ll = long long; int H,W; #define MAX_N 202 int board[MAX_N][MAX_N]; //Union-Find木 template <int NV = MAX_N> class UFind{ //vector <int> par; pair <int,int> par[MAX_N][MAX_N]; set <pair <int,int> > adj[MAX_N][MAX_N]; //vector <int> myrank; public: int color[MAX_N][MAX_N]; UFind(){ rep(i,NV){ rep(j,NV){ par[i][j] = mp(i,j); } } } inline pair <int,int> find(pair <int, int> x){//木の根を求める if (par[x.fir][x.sec] == x) { return x; }else{ return par[x.fir][x.sec] = find(par[x.fir][x.sec]); } } inline void unite(pair <int,int> x, pair <int,int> y) {//xとyの属する集合を併合 x = find(x); y = find(y); if (x == y) { return; } if (sz(adj[x.fir][x.sec]) > sz(adj[y.fir][y.sec])) { swap(x,y); } // y <- x par[x.fir][x.sec] = y; adj[y.fir][y.sec].insert(ALL(adj[x.fir][x.sec])); adj[x.fir][x.sec].clear(); } inline void add(pair <int,int> x, pair <int,int> y) { //x <- y x = find(x); y = find(y); if (x == y) { return; } adj[x.fir][x.sec].insert(y); } inline bool same(pair <int,int> x, pair <int,int> y) {//x,yが同じ集合に属するか否か return find(x) == find(y); } inline int getcolor(pair <int,int> x){ x = find(x); return color[x.fir][x.sec]; } inline void update(pair <int,int> root, int X) { vector <pair <int,int> >cur_adj(ALL(adj[root.fir][root.sec])); for (auto &a : cur_adj) { a = find(a); } color[root.fir][root.sec] = X; sort(ALL(cur_adj));cur_adj.erase(unique(ALL(cur_adj)), cur_adj.end()); root = find(root); adj[root.fir][root.sec].clear(); adj[root.fir][root.sec].insert(ALL(cur_adj)); for (auto &a : cur_adj) { if (getcolor(a) == X) { unite(a, root); } } root = find(root); color[root.fir][root.sec] = X; //DEBUG1(root); } inline void dbg(){ rep(i,H){ rep(j,W){ auto mypar = find(mp(i,j)); //auto col = getcolor(mp(i,j)); DEBUG4(i,j,mypar,adj[i][j]); } } } }; //Union-find木終わり UFind <> UF; inline bool OK(int x, int y) { return 0 <= x && x < H && 0 <= y && y < W; } inline void paint(int R, int C, int X){ auto root = UF.find(mp(R,C)); if (UF.getcolor(root) == X) { return; } UF.update(root,X); } int main() { cin.tie(0); ios_base::sync_with_stdio(0); cin >> H >> W; rep(i,H){ rep(j,W){ cin >> board[i][j]; UF.color[i][j] = board[i][j]; } } int dx[] = {-1,0,0,1}; int dy[] = {0,1,-1,0}; //int dx[] = {0,1}; //int dy[] = {1,0}; rep(i,H){ rep(j,W){ rep(k,4){ int nx = i + dx[k], ny = j + dy[k]; if (OK(nx, ny)) { if (board[nx][ny] == board[i][j]) { UF.unite(mp(i,j), mp(nx,ny)); }else{ UF.add(mp(i,j), mp(nx,ny)); } } } } } //UF.dbg(); int Q; cin >> Q; while(Q--){ int R,C,X; cin >> R >> C >> X; R--;C--; paint(R,C,X); //DEBUG3(R,C,X); /* rep(i,H){ rep(j,W){ if (j) cout << ' '; if (i == R && j == C) { cout << '*'; continue; } cout << board[i][j]; } cout << "\t"; */ if (Q == 0) { rep(i,H){ rep(j,W){ if (j) cout << ' '; char c = UF.getcolor(mp(i,j)) + '0'; cout << c; } cout << endl; } } } return 0; }