結果

問題 No.2238 Rock and Hole
ユーザー no wayno way
提出日時 2023-03-03 23:06:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 68 ms / 3,000 ms
コード長 1,883 bytes
コンパイル時間 1,886 ms
コンパイル使用メモリ 172,360 KB
実行使用メモリ 14,484 KB
最終ジャッジ日時 2023-10-18 03:26:18
合計ジャッジ時間 3,297 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
7,812 KB
testcase_01 AC 3 ms
7,812 KB
testcase_02 AC 3 ms
9,848 KB
testcase_03 AC 3 ms
7,808 KB
testcase_04 AC 3 ms
7,812 KB
testcase_05 AC 3 ms
7,812 KB
testcase_06 AC 4 ms
9,848 KB
testcase_07 AC 3 ms
9,848 KB
testcase_08 AC 3 ms
9,848 KB
testcase_09 AC 3 ms
7,812 KB
testcase_10 AC 4 ms
9,852 KB
testcase_11 AC 6 ms
11,912 KB
testcase_12 AC 5 ms
11,904 KB
testcase_13 AC 5 ms
11,916 KB
testcase_14 AC 4 ms
9,856 KB
testcase_15 AC 4 ms
9,864 KB
testcase_16 AC 9 ms
14,484 KB
testcase_17 AC 8 ms
14,472 KB
testcase_18 AC 5 ms
10,564 KB
testcase_19 AC 68 ms
12,236 KB
testcase_20 AC 9 ms
12,264 KB
testcase_21 AC 12 ms
10,536 KB
testcase_22 AC 7 ms
12,240 KB
testcase_23 AC 3 ms
7,812 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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");
}
0