提出 #20093372

ソースコード 拡げる

#!/usr/local/bin/pypy3
import sys
readline = sys.stdin.buffer.readline

class unionfind:
	def __init__(self,n):
		self.p=[-1]*n
		self.s=[1]*n
		self.c=n
	
	def find(self,a):
		if self.p[a]==-1:
			return a
		else:
			self.p[a]=self.find(self.p[a])
			return self.p[a]
	
	def unite(self,a,b):
		a=self.find(a)
		b=self.find(b)
		if a==b:
			return False;
		self.p[b]=a;
		self.s[a]+=self.s[b];
		self.c-=1;
		return True;

h,w=map(int,readline().split())
s=[readline().decode('utf-8') for _ in range(h)]

ans=10**9

uf=unionfind(h+w)
for i in range(h):
	for j in range(w):
		if s[i][j]=='#':
			uf.unite(i,h+j)
uf.unite(0,h)
uf.unite(h-1,h)
uf.unite(0,h+w-1)
uf.unite(h-1,h+w-1)

for k in range(2):
	ls=[0]*(h+w)
	if k==0:
		for i in range(h):
			ls[uf.find(i)]=1
	else:
		for i in range(h,h+w):
			ls[uf.find(i)]=1
	ans=min(ans,sum(ls)-1)

print(ans)

提出情報

提出日時
問題 D - Skate
ユーザ maroonrk_admin
言語 PyPy3 (7.3.0)
得点 600
コード長 907 Byte
結果 AC
実行時間 146 ms
メモリ 126432 KiB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 600 / 600
結果
AC × 2
AC × 37
セット名 テストケース
Sample sample.txt, sample_2.txt
All complete_1000_1000.txt, complete_1000_1000_1.txt, complete_1000_1000_10.txt, complete_1000_1000_100.txt, complete_1000_1000_1000.txt, complete_1000_1000_3.txt, complete_1000_1000_333.txt, complete_1000_1000_5.txt, complete_1000_1000_7.txt, horizontal_820_2_1.txt, horizontal_86_2_2.txt, horizontal_892_2_0.txt, random_1000_1000.txt, random_1000_1000_2.txt, random_1000_1000_3.txt, random_1000_1000_4.txt, random_1000_1000_5.txt, random_391_910.txt, random_423_172.txt, random_45_809.txt, random_461_111.txt, random_740_398.txt, sample.txt, sample_2.txt, sparse_261_351.txt, sparse_292_662.txt, sparse_372_354.txt, sparse_381_830.txt, sparse_432_398.txt, sparse_626_931.txt, sparse_73_682.txt, sparse_801_149.txt, sparse_820_852.txt, sparse_85_950.txt, vertical_2_113_1.txt, vertical_2_304_2.txt, vertical_2_710_0.txt
ケース名 結果 実行時間 メモリ
complete_1000_1000.txt AC 146 ms 126432 KiB
complete_1000_1000_1.txt AC 116 ms 97116 KiB
complete_1000_1000_10.txt AC 89 ms 74188 KiB
complete_1000_1000_100.txt AC 81 ms 70148 KiB
complete_1000_1000_1000.txt AC 76 ms 68812 KiB
complete_1000_1000_3.txt AC 105 ms 84200 KiB
complete_1000_1000_333.txt AC 79 ms 69164 KiB
complete_1000_1000_5.txt AC 93 ms 72320 KiB
complete_1000_1000_7.txt AC 90 ms 72912 KiB
horizontal_820_2_1.txt AC 58 ms 66252 KiB
horizontal_86_2_2.txt AC 54 ms 62312 KiB
horizontal_892_2_0.txt AC 61 ms 66308 KiB
random_1000_1000.txt AC 73 ms 68672 KiB
random_1000_1000_2.txt AC 79 ms 69144 KiB
random_1000_1000_3.txt AC 80 ms 69016 KiB
random_1000_1000_4.txt AC 85 ms 70020 KiB
random_1000_1000_5.txt AC 77 ms 69128 KiB
random_391_910.txt AC 73 ms 68584 KiB
random_423_172.txt AC 59 ms 65840 KiB
random_45_809.txt AC 60 ms 64328 KiB
random_461_111.txt AC 57 ms 65956 KiB
random_740_398.txt AC 64 ms 68240 KiB
sample.txt AC 50 ms 61972 KiB
sample_2.txt AC 60 ms 61968 KiB
sparse_261_351.txt AC 59 ms 65628 KiB
sparse_292_662.txt AC 59 ms 65940 KiB
sparse_372_354.txt AC 61 ms 65816 KiB
sparse_381_830.txt AC 60 ms 68140 KiB
sparse_432_398.txt AC 60 ms 65712 KiB
sparse_626_931.txt AC 69 ms 68392 KiB
sparse_73_682.txt AC 56 ms 64496 KiB
sparse_801_149.txt AC 57 ms 65912 KiB
sparse_820_852.txt AC 71 ms 68636 KiB
sparse_85_950.txt AC 58 ms 64584 KiB
vertical_2_113_1.txt AC 52 ms 62044 KiB
vertical_2_304_2.txt AC 56 ms 62096 KiB
vertical_2_710_0.txt AC 55 ms 64220 KiB