結果
問題 | No.348 カゴメカゴメ |
ユーザー | beet |
提出日時 | 2019-01-28 19:57:35 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 481 ms / 2,000 ms |
コード長 | 2,814 bytes |
コンパイル時間 | 2,913 ms |
コンパイル使用メモリ | 223,456 KB |
最終ジャッジ日時 | 2025-01-06 20:41:40 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 53 |
ソースコード
#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+1); s[0]=string(w,'.'); for(Int i=1;i<h;i++) cin>>s[i],s[i]='.'+s[i]+'.'; s[h++]=string(w,'.'); 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; }