結果
問題 | No.307 最近色塗る問題多くない? |
ユーザー | IL_msta |
提出日時 | 2015-11-28 18:11:11 |
言語 | C++11 (gcc 11.4.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 4,398 bytes |
コンパイル時間 | 1,272 ms |
コンパイル使用メモリ | 114,192 KB |
実行使用メモリ | 196,096 KB |
最終ジャッジ日時 | 2024-09-14 04:57:07 |
合計ジャッジ時間 | 8,122 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,940 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 3 ms
6,948 KB |
testcase_05 | AC | 2 ms
6,944 KB |
testcase_06 | AC | 2 ms
6,940 KB |
testcase_07 | AC | 7 ms
6,944 KB |
testcase_08 | AC | 35 ms
6,940 KB |
testcase_09 | AC | 17 ms
6,944 KB |
testcase_10 | AC | 10 ms
6,940 KB |
testcase_11 | AC | 31 ms
7,296 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 11 ms
6,940 KB |
testcase_14 | AC | 4 ms
6,948 KB |
testcase_15 | AC | 5 ms
6,940 KB |
testcase_16 | AC | 3 ms
6,940 KB |
testcase_17 | AC | 11 ms
6,940 KB |
testcase_18 | AC | 16 ms
6,944 KB |
testcase_19 | AC | 19 ms
6,940 KB |
testcase_20 | AC | 3 ms
6,940 KB |
testcase_21 | AC | 18 ms
6,944 KB |
testcase_22 | AC | 238 ms
6,940 KB |
testcase_23 | AC | 16 ms
6,940 KB |
testcase_24 | AC | 16 ms
6,944 KB |
testcase_25 | AC | 26 ms
6,944 KB |
testcase_26 | AC | 26 ms
6,944 KB |
testcase_27 | AC | 87 ms
25,600 KB |
testcase_28 | AC | 908 ms
196,096 KB |
testcase_29 | RE | - |
testcase_30 | AC | 27 ms
6,940 KB |
testcase_31 | AC | 124 ms
34,688 KB |
testcase_32 | AC | 23 ms
6,940 KB |
testcase_33 | WA | - |
testcase_34 | AC | 1,275 ms
6,940 KB |
testcase_35 | AC | 1,271 ms
6,940 KB |
ソースコード
#define _USE_MATH_DEFINES #include <iostream> #include <iomanip> #include <sstream> #include <algorithm> #include <cmath> #include <string> #include <queue> #include <vector> #include <complex> #include <set> #include <map> #include <stack> #include <list> #include <valarray> #include<cassert>//assert(); //#include <random>//xAOJ ///////// #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define P(p) cout<<(p)<<endl; #define PII pair<int,int> ///////// typedef long long LL; typedef long double LD; typedef unsigned long long ULL; ///////// using namespace::std; ///////// ///////// class UnionFind{ public: int cNum;//要素数 int cSize;// vector<int> parent; vector<int> rank; vector<bool> color; vector< vector< int > > tonari; UnionFind(int n){ cNum = n; cSize = n; parent = vector<int>(n); rank = vector<int>(n,0); color = vector<bool>(n); tonari = vector< vector<int> >(n); for(int i=0;i<n;++i){parent[i] = i;} } int find(int x){ if( parent[x] == x ){return x;} return parent[x] = find( parent[x] ); } bool same(int x,int y){return find(x) == find(y);} void add(int x,int y){//union yの方に結びつけ --cSize; x = find(x); y = find(y); if( x==y )return; if( rank[x] == rank[y] ){ parent[x] = y; ++rank[y]; } if( rank[x] < rank[y] ){ parent[x] = y; }else{ parent[y] = x; swap(x,y); } ////// vector<int> temp; vector<int>::iterator it,endit; it = tonari[x].begin(); endit = tonari[x].end(); for(;it != endit;++it){ if( !same(y,*it) ){ temp.push_back(*it); } } tonari[x].clear(); it = tonari[y].begin(); endit = tonari[y].end(); for(;it != endit;++it){ if( !same(y,*it) ){ temp.push_back(*it); } } sort( temp.begin(), temp.end() ); temp.erase( unique( temp.begin(), temp.end() ), temp.end() ); tonari[y].swap( temp ); } void addVec(int x, vector<int>& Vec){ vector<int>::iterator it,endit; vector<int>::iterator it2,endit2; vector<int> temp; int ter; it = Vec.begin(); endit = Vec.end(); for(;it != endit;++it){ ter = find(*it); it2 = tonari[ ter ].begin(); endit2 = tonari[ ter ].end(); temp.insert( temp.end(), it2, endit2 ); tonari[ ter ].clear(); } it = Vec.begin(); endit = Vec.end(); for(;it != endit;++it){ parent[ find(*it) ] = x; } vector<int> temp2; it = temp.begin(); endit = temp.end(); for(;it != endit; ++it){ if( !same(x,*it) ){ temp2.push_back( *it ); } } temp.swap( temp2 ); sort( temp.begin(), temp.end() ); temp.erase( unique( temp.begin(), temp.end() ), temp.end() ); tonari[x].swap( temp ); } void tonariAdd(int atti,int kotti){ tonari[ find(atti) ].push_back(kotti); tonari[ find(kotti) ].push_back(atti); } }; void solve(){ int H,W; cin >> H >> W; UnionFind UF(H*W); int incolor; for(int h=0;h<H;++h){ for(int w=0;w<W;++w){ cin >> incolor; if( incolor == 1 ){ UF.color[h*W + w] = true; }else{ UF.color[h*W + w] = false; } } } //////////////// if( 1<H && UF.color[0] == UF.color[1] ){ UF.add(0,1); }else{ UF.tonariAdd(0,1); } if( 1<W && UF.color[0] == UF.color[W] ){ UF.add(0,W); }else{ UF.tonariAdd(0,W); } for(int h=0;h<H;++h){ for(int w=0;w<W;++w){ if( h> 0 ){ if( UF.color[h*W+w] == UF.color[(h-1)*W + w] ){ UF.add(h*W+w,(h-1)*W+w ); }else{ UF.tonariAdd(h*W+w,(h-1)*W+w); } } if( w> 0 ){ if( UF.color[h*W+w] == UF.color[h*W+(w-1)] ){ UF.add( h*W+w,h*W+(w-1) ); }else{ UF.tonariAdd(h*W+w,h*W+(w-1) ); } } } } //////////////// int Q; cin >> Q; int R,C,Xnum; bool X; int ter; vector<int> tempVec; tempVec.reserve(H*W); while(Q--){ cin >> R >> C >> Xnum; --R;--C; if( Xnum == 1 ){ X = true; }else{ X = false; } ter = UF.find(R*W+C); if( UF.color[ ter ] == X ) continue; UF.color[ter] = X; if( UF.cSize == 1 ){ continue;} tempVec.clear(); tempVec.swap( UF.tonari[ ter ] ); UF.addVec(ter, tempVec); } for(int h=0;h<H;++h){ for(int w = 0;w<W;++w){ if( w != 0 ){ cout << ' '; } if( UF.color[ UF.find(h*W+w) ] ){ cout << 1; }else{ cout << 0; } } cout << endl; } } int main(void){ std::cin.tie(0); std::ios::sync_with_stdio(false); std::cout << std::fixed;// //cout << setprecision(16);// //cpp solve(); return 0; }