結果
問題 | No.348 カゴメカゴメ |
ユーザー | beet |
提出日時 | 2019-01-28 19:55:09 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
RE
|
実行時間 | - |
コード長 | 2,812 bytes |
コンパイル時間 | 2,467 ms |
コンパイル使用メモリ | 233,928 KB |
実行使用メモリ | 131,388 KB |
最終ジャッジ日時 | 2024-10-05 11:44:29 |
合計ジャッジ時間 | 14,981 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | RE | - |
testcase_01 | RE | - |
testcase_02 | RE | - |
testcase_03 | RE | - |
testcase_04 | RE | - |
testcase_05 | RE | - |
testcase_06 | RE | - |
testcase_07 | RE | - |
testcase_08 | RE | - |
testcase_09 | RE | - |
testcase_10 | RE | - |
testcase_11 | RE | - |
testcase_12 | RE | - |
testcase_13 | RE | - |
testcase_14 | RE | - |
testcase_15 | RE | - |
testcase_16 | RE | - |
testcase_17 | RE | - |
testcase_18 | RE | - |
testcase_19 | RE | - |
testcase_20 | RE | - |
testcase_21 | RE | - |
testcase_22 | RE | - |
testcase_23 | RE | - |
testcase_24 | RE | - |
testcase_25 | RE | - |
testcase_26 | RE | - |
testcase_27 | RE | - |
testcase_28 | RE | - |
testcase_29 | RE | - |
testcase_30 | RE | - |
testcase_31 | RE | - |
testcase_32 | RE | - |
testcase_33 | RE | - |
testcase_34 | RE | - |
testcase_35 | RE | - |
testcase_36 | RE | - |
testcase_37 | RE | - |
testcase_38 | RE | - |
testcase_39 | RE | - |
testcase_40 | RE | - |
testcase_41 | RE | - |
testcase_42 | RE | - |
testcase_43 | RE | - |
testcase_44 | RE | - |
testcase_45 | RE | - |
testcase_46 | RE | - |
testcase_47 | RE | - |
testcase_48 | RE | - |
testcase_49 | RE | - |
testcase_50 | RE | - |
testcase_51 | RE | - |
testcase_52 | RE | - |
ソースコード
#include<bits/stdc++.h> using namespace std; using Int = long long; template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;} template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;} struct UnionFind{ Int n; vector<Int> r,p; UnionFind(){} UnionFind(Int sz):n(sz),r(sz,1),p(sz,0){iota(p.begin(),p.end(),0);} Int find(Int x){ return (x==p[x]?x:p[x]=find(p[x])); } bool same(Int x,Int y){ return find(x)==find(y); } void unite(Int x,Int y){ x=find(x);y=find(y); if(x==y) return; if(r[x]<r[y]) swap(x,y); r[x]+=r[y]; p[y]=x; } }; //INSERT ABOVE HERE signed main(){ Int h,w; cin>>h>>w; h++;w+=2; vector<string> s(h); s[0]=string(w,'.'); s[h++]=string(w,'.'); for(Int i=1;i<h;i++) cin>>s[i],s[i]='.'+s[i]+'.'; Int n=h*w; UnionFind uf(n); auto idx=[&](Int i,Int j){return i*w+j;}; for(Int i=0;i<h;i++) for(Int j=0;j<w;j++) uf.r[idx(i,j)]=s[i][j]=='x'; for(Int i=0;i<h;i++){ for(Int j=0;j<w;j++){ if(s[i][j]!='x') continue; if(i+1<h&&s[i+1][j]=='x') uf.unite(idx(i,j),idx(i+1,j)); if(j+1<w&&s[i][j+1]=='x') uf.unite(idx(i,j),idx(i,j+1)); if(i+1< h&&j+1<w&&s[i+1][j+1]=='x') uf.unite(idx(i,j),idx(i+1,j+1)); if(i-1>=0&&j+1<w&&s[i-1][j+1]=='x') uf.unite(idx(i,j),idx(i-1,j+1)); } } set<Int> ss; for(Int i=0;i<h;i++) for(Int j=0;j<w;j++) if(s[i][j]=='x') ss.emplace(uf.find(idx(i,j))); for(Int i=0;i<h;i++) for(Int j=0;j<w;j++) if(s[i][j]=='x') assert(uf.r[uf.find(idx(i,j))]>1); vector<set<Int> > G(n); vector<Int> sz(n); Int dy[]={0,0,1,-1}; Int dx[]={1,-1,0,0}; vector<Int> used(n,0); auto in=[&](Int y,Int x){return 0<=y&&y<h&&0<=x&&x<w;}; using T = tuple<Int, Int, Int>; queue<T> qt; qt.emplace(0,0,uf.find(0)); while(!qt.empty()){ Int sy,sx,c; tie(sy,sx,c)=qt.front();qt.pop(); using P = pair<Int, Int>; queue<P> q; used[idx(sy,sx)]=1; q.emplace(sy,sx); while(!q.empty()){ Int y,x; tie(y,x)=q.front();q.pop(); for(Int k=0;k<4;k++){ Int ny=y+dy[k],nx=x+dx[k]; Int nz=idx(ny,nx); if(!in(ny,nx)||used[nz]) continue; if(s[ny][nx]=='x'&&!uf.same(c,nz)){ G[c].emplace(uf.find(nz)); qt.emplace(ny,nx,uf.find(nz)); }else{ used[nz]=1; q.emplace(ny,nx); } } } } vector<Int> dp1(n,0),dp2(n,0); function<void(Int)> dfs= [&](Int v)->void{ dp1[v]=uf.r[v]; for(Int u:G[v]){ dfs(u); dp1[v]+=dp2[u]; dp2[v]+=dp1[u]; } chmax(dp1[v],dp2[v]); }; dfs(0); cout<<dp1[0]<<endl; return 0; }