提出 #37972304

ソースコード 拡げる

#include<bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;

int main(){
	int h,w;
	cin >> h >> w;
	
	vector<string>b(h);
	for(int i=0;i<h;i++)cin >> b[i];
	
	atcoder::mf_graph<int>g(h*w+4);
	// hw,hw+2 - left - right - hw+1,hw+3
	
	int s=h*w,t=s+1;
	int s2=s+2,t2=t+2;
	int left2=0,right2=0;
	
	for(int i=0;i<h;i++){
		for(int j=i%2;j<w;j+=2){
			//left
			if(b[i][j]=='2'){
				g.add_edge(s2,i*w+j,1);
				left2++;
			}
			if(b[i][j]=='?'){
				g.add_edge(s,i*w+j,1);
			}
			//left to right
			if(i+1<h &&b[i][j]!='1'&&b[i+1][j]!='1')g.add_edge(i*w+j,(i+1)*w+j,1);
			if(j+1<w &&b[i][j]!='1'&&b[i][j+1]!='1')g.add_edge(i*w+j,i*w+(j+1),1);
			if(i-1>=0&&b[i][j]!='1'&&b[i-1][j]!='1')g.add_edge(i*w+j,(i-1)*w+j,1);
			if(j-1>=0&&b[i][j]!='1'&&b[i][j-1]!='1')g.add_edge(i*w+j,i*w+(j-1),1);
		}
		//right
		for(int j=1-i%2;j<w;j+=2){
			if(b[i][j]=='2'){
				g.add_edge(i*w+j,t2,1);
				right2++;
			}
			if(b[i][j]=='?'){
				g.add_edge(i*w+j,t,1);
			}
		}
	}
	
	g.add_edge(s,t2,left2);
	g.add_edge(s2,t,right2);
	
	int x=g.flow(s2,t2);
	int y=g.flow(s,t2);
	int z=g.flow(s2,t);
	
	if(x+y==left2+right2&&x+z==left2+right2)cout << "Yes" << endl;
	else cout << "No" << endl;
	
}

提出情報

提出日時
問題 G - Tatami
ユーザ kyopro_friends
言語 C++ (GCC 9.2.1)
得点 600
コード長 1246 Byte
結果 AC
実行時間 123 ms
メモリ 15104 KiB

ジャッジ結果

セット名 Sample All AfterContest
得点 / 配点 0 / 0 600 / 600 0 / 0
結果
AC × 3
AC × 42
AC × 2
セット名 テストケース
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, random_21.txt, random_22.txt, random_23.txt, random_24.txt, random_25.txt, random_26.txt, random_27.txt, random_28.txt, random_29.txt, random_30.txt, random_31.txt, random_32.txt, sample_01.txt, sample_02.txt, sample_03.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt
AfterContest after_contest_01.txt, after_contest_02.txt
ケース名 結果 実行時間 メモリ
after_contest_01.txt AC 8 ms 3588 KiB
after_contest_02.txt AC 20 ms 8548 KiB
hand_01.txt AC 4 ms 3544 KiB
hand_02.txt AC 1 ms 3484 KiB
hand_03.txt AC 4 ms 3488 KiB
hand_04.txt AC 2 ms 3652 KiB
hand_05.txt AC 2 ms 3660 KiB
hand_06.txt AC 3 ms 3492 KiB
hand_07.txt AC 2 ms 3624 KiB
random_01.txt AC 111 ms 15104 KiB
random_02.txt AC 76 ms 11780 KiB
random_03.txt AC 6 ms 4440 KiB
random_04.txt AC 70 ms 10728 KiB
random_05.txt AC 105 ms 14832 KiB
random_06.txt AC 80 ms 11864 KiB
random_07.txt AC 20 ms 5340 KiB
random_08.txt AC 18 ms 5544 KiB
random_09.txt AC 123 ms 14928 KiB
random_10.txt AC 20 ms 5356 KiB
random_11.txt AC 32 ms 6132 KiB
random_12.txt AC 16 ms 4828 KiB
random_13.txt AC 112 ms 14952 KiB
random_14.txt AC 37 ms 6536 KiB
random_15.txt AC 41 ms 7532 KiB
random_16.txt AC 36 ms 6780 KiB
random_17.txt AC 91 ms 14980 KiB
random_18.txt AC 14 ms 4536 KiB
random_19.txt AC 87 ms 14536 KiB
random_20.txt AC 15 ms 4848 KiB
random_21.txt AC 95 ms 15028 KiB
random_22.txt AC 45 ms 8460 KiB
random_23.txt AC 21 ms 6024 KiB
random_24.txt AC 8 ms 4196 KiB
random_25.txt AC 29 ms 6744 KiB
random_26.txt AC 16 ms 4772 KiB
random_27.txt AC 66 ms 11820 KiB
random_28.txt AC 6 ms 4020 KiB
random_29.txt AC 9 ms 4280 KiB
random_30.txt AC 15 ms 4888 KiB
random_31.txt AC 8 ms 4232 KiB
random_32.txt AC 29 ms 8904 KiB
sample_01.txt AC 3 ms 3588 KiB
sample_02.txt AC 2 ms 3552 KiB
sample_03.txt AC 2 ms 3536 KiB