結果
問題 | No.2238 Rock and Hole |
ユーザー |
|
提出日時 | 2023-03-03 23:06:55 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 63 ms / 3,000 ms |
コード長 | 1,883 bytes |
コンパイル時間 | 1,748 ms |
コンパイル使用メモリ | 173,092 KB |
実行使用メモリ | 12,856 KB |
最終ジャッジ日時 | 2024-09-18 00:16:26 |
合計ジャッジ時間 | 2,487 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include<bits/stdc++.h> using namespace std; const int N=2e5+10; struct node{ int u,to,w; }edge[N<<5]; char s[N]; int head[N],arrange[N],cur[N],r[N],c[N],f[N],g[N]; int n,m,x,y,z,k,S,T; void add(int x,int y,int z) { edge[k].u=y; edge[k].to=head[x]; edge[k].w=z; head[x]=k++; edge[k].u=x; edge[k].to=head[y]; edge[k].w=0; head[y]=k++; } bool bfs(){ memset(arrange,0,sizeof(arrange)); queue<int>q; q.push(S); arrange[S]=1; while (!q.empty()) { int v=q.front(); q.pop(); if (T==v) return 1; for (int i=head[v];i!=-1;i=edge[i].to) { int u=edge[i].u; if (arrange[u]||!edge[i].w) continue; arrange[u]=arrange[v]+1; q.push(u); } } return 0; } int dfs(int now,int maxlow,int t){ if (now==t) return maxlow; int ret=0; for (int &i=cur[now];i!=-1;i=edge[i].to) { int u=edge[i].u; if (arrange[u]!=arrange[now]+1||!edge[i].w) continue; int f=dfs(u,min(maxlow-ret,edge[i].w),t); edge[i].w-=f; edge[i^1].w+=f; ret+=f; if (f==maxlow) return maxlow; } return ret; } int dinic(){ int ans=0; while (bfs()) { memcpy(cur,head,sizeof(head)); ans+=dfs(S,0x3f3f3f3f,T); } return ans; } int get(int x,int y){ return (x-1)*m+y; } int main(){ scanf("%d%d",&n,&m); S=n*m+1; T=n*m+2; int sum=0; memset(head,-1,sizeof(head)); for (int i=1;i<=n;i++){ scanf("%s",s+1); for (int j=1;j<=m;j++) if (s[j]=='r'){ add(S,get(i,j),1); if (r[i]) add(get(i,j),r[i],1); if (c[j]) add(get(i,j),c[j],1); sum++; g[get(i,j)]=1; }else if (s[j]=='h'){ f[get(i,j)]=1; add(get(i,j),T,1); r[i]=get(i,j); c[j]=get(i,j); } } for (int i=1;i<=n;i++) r[i]=0; for (int i=1;i<=m;i++) c[i]=0; for (int i=n;i>=1;i--) for (int j=m;j>=1;j--) if (g[get(i,j)]){ if (r[i]) add(get(i,j),r[i],1); if (c[j]) add(get(i,j),c[j],1); }else if (f[get(i,j)]){ r[i]=get(i,j); c[j]=get(i,j); } if (dinic()==sum) puts("Yes"); else puts("No"); }