Submission #13406078


Source Code Expand

Copy
# Studying https://atcoder.jp/contests/abc168/tasks/abc168_f
#      and https://mobile.twitter.com/chokudai/status/1262023105888698369

N,M = gets.split.map(&:to_i)
縦線 = N.times.map{ gets.split.map(&:to_i) }
横線 = M.times.map{ gets.split.map(&:to_i) }

経線 = 縦線.map{|_,_,c| c }.uniq.sort
緯線 = 横線.map{|d,| d }.uniq.sort

GW = 経線.size*2+3 # INF ゾーンと壁で囲います(+4)。
GH = 緯線.size*2+3
GI = lambda{|横,縦|
	i = 経線.bsearch_index{|_| 横<=_ }||経線.size # 線分の端点の座標に対応する
	j = 緯線.bsearch_index{|_| 縦<=_ }||緯線.size
	i1 = 経線[i] != 横 ? 1 : 0 # 線分間の座標に対応するための補正
	j1 = 緯線[j] != 縦 ? 1 : 0
	next (2+2*j-j1)*GW+(2+2*i-i1)
}
下 = lambda{|i|
	(i/GW+1)/2*2*GW + i%GW
}
上 = lambda{|i|
	i/GW/2*2*GW + i%GW
}
右 = lambda{|i|
	(i+1)/2*2
}
左 = lambda{|i|
	i/2*2
}
Grid = lambda{|g|
	縦線.each{|a,b,c|
		下[GI[c,a]].step(上[GI[c,b]], GW){|i|
			g[i] = '0'
		}
	}
	i = 0
	GH.times{
		g[i] = g[i+GW-1] = '0'
		i += GW
	}

	横線.each{|d,e,f|
		右[GI[e,d]].upto(左[GI[f,d]]){|i|
			g[i] = '0'
		}
	}
	0.upto(GW-1){|i|
		g[i] = g[-1-i] = '0'
	}

	return g
}['1'*(GW*GH)]
Area = lambda{|a|
	(GW+1).upto(GW+GW-2){|i|
		a[i] = a[-1-i] = Float::INFINITY
	}
	i = GW+1
	(GH-2).times{
		a[i] = a[i+GW-3] = Float::INFINITY
		i += GW
	}

	heights = 緯線.each_cons(2).map{|y,z| z-y }
	widths = 経線.each_cons(2).map{|y,z| z-y }
	j = (GW+1)*3
	heights.each{|h|
		i = 0
		widths.each{|w|
			a[j+i] = h*w
			i += 2
		}
		j += GW+GW
	}

	return a
}[[0]*(GW*GH)]

area = 0
cow = GI[0,0]
Grid[cow] = '0'
Q = [cow]
while at = Q.shift
	area += Area[at]
	[-1,1,GW,-GW].each{|mv|
		next if Grid[at+mv] == '0'
		Grid[at+mv] = '0'
		Q << at+mv
	}
end

puts(area.finite? ? area : 'INF')

Submission Info

Submission Time
Task F - . (Single Dot)
User ds14050
Language Ruby (2.7.1)
Score 600
Code Size 1879 Byte
Status
Exec Time 2489 ms
Memory 50112 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt
Subtask1 600 / 600 sample_01.txt, sample_02.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt, sub1_36.txt, sub1_37.txt, sub1_38.txt, sub1_39.txt, sub1_40.txt, sub1_41.txt, sub1_42.txt, sub1_43.txt, sub1_44.txt, sub1_45.txt, sub1_46.txt, sub1_47.txt, sub1_48.txt, sub1_49.txt, sub1_50.txt, sub1_51.txt, sub1_52.txt, sub1_53.txt, sub1_54.txt, sub1_55.txt, sub1_56.txt, sub1_57.txt, sub1_58.txt, sub1_59.txt, sub1_60.txt, sub1_61.txt, sub1_62.txt, sub1_63.txt, sub1_64.txt, sub1_65.txt, sub1_66.txt, sub1_67.txt, sub1_68.txt, sub1_69.txt, sub1_70.txt, sub1_71.txt, sub1_72.txt, sub1_73.txt, sub1_74.txt, sub1_75.txt, sub1_76.txt, sub1_77.txt, sub1_78.txt, sub1_79.txt, sub1_80.txt, sub1_81.txt, sub1_82.txt, sub1_83.txt, sub1_84.txt, sub1_85.txt, sub1_86.txt, sub1_87.txt, sub1_88.txt, sub1_89.txt, sub1_90.txt, sub1_91.txt, sub1_92.txt, sub1_93.txt, sub1_94.txt
Case Name Status Exec Time Memory
sample_01.txt 53 ms 14428 KB
sample_02.txt 51 ms 14496 KB
sub1_01.txt 113 ms 25360 KB
sub1_02.txt 89 ms 19968 KB
sub1_03.txt 74 ms 18096 KB
sub1_04.txt 68 ms 16096 KB
sub1_05.txt 189 ms 36124 KB
sub1_06.txt 82 ms 18712 KB
sub1_07.txt 97 ms 20020 KB
sub1_08.txt 58 ms 14876 KB
sub1_09.txt 90 ms 19324 KB
sub1_10.txt 254 ms 40964 KB
sub1_11.txt 57 ms 14604 KB
sub1_12.txt 57 ms 14432 KB
sub1_13.txt 56 ms 14280 KB
sub1_14.txt 52 ms 14524 KB
sub1_15.txt 54 ms 14380 KB
sub1_16.txt 52 ms 14344 KB
sub1_17.txt 173 ms 49872 KB
sub1_18.txt 1612 ms 49560 KB
sub1_19.txt 1664 ms 49152 KB
sub1_20.txt 2400 ms 49804 KB
sub1_21.txt 2039 ms 47080 KB
sub1_22.txt 1265 ms 48832 KB
sub1_23.txt 2079 ms 49408 KB
sub1_24.txt 1326 ms 49936 KB
sub1_25.txt 2303 ms 49736 KB
sub1_26.txt 1768 ms 50112 KB
sub1_27.txt 381 ms 45320 KB
sub1_28.txt 477 ms 45612 KB
sub1_29.txt 243 ms 46324 KB
sub1_30.txt 369 ms 46036 KB
sub1_31.txt 149 ms 45956 KB
sub1_32.txt 2113 ms 44840 KB
sub1_33.txt 472 ms 46148 KB
sub1_34.txt 562 ms 45844 KB
sub1_35.txt 1130 ms 45336 KB
sub1_36.txt 550 ms 46192 KB
sub1_37.txt 1869 ms 49344 KB
sub1_38.txt 161 ms 17048 KB
sub1_39.txt 110 ms 15168 KB
sub1_40.txt 1474 ms 50088 KB
sub1_41.txt 177 ms 17000 KB
sub1_42.txt 52 ms 14452 KB
sub1_43.txt 55 ms 14484 KB
sub1_44.txt 53 ms 14376 KB
sub1_45.txt 54 ms 14588 KB
sub1_46.txt 52 ms 14280 KB
sub1_47.txt 139 ms 15848 KB
sub1_48.txt 112 ms 15780 KB
sub1_49.txt 141 ms 15932 KB
sub1_50.txt 117 ms 15952 KB
sub1_51.txt 150 ms 15808 KB
sub1_52.txt 138 ms 15788 KB
sub1_53.txt 142 ms 15624 KB
sub1_54.txt 126 ms 15828 KB
sub1_55.txt 1793 ms 49748 KB
sub1_56.txt 1596 ms 49784 KB
sub1_57.txt 2489 ms 49668 KB
sub1_58.txt 1507 ms 49772 KB
sub1_59.txt 1556 ms 49376 KB
sub1_60.txt 2348 ms 49664 KB
sub1_61.txt 638 ms 25916 KB
sub1_62.txt 1642 ms 46604 KB
sub1_63.txt 61 ms 14564 KB
sub1_64.txt 1597 ms 37456 KB
sub1_65.txt 89 ms 15200 KB
sub1_66.txt 1053 ms 34320 KB
sub1_67.txt 122 ms 15920 KB
sub1_68.txt 375 ms 20864 KB
sub1_69.txt 639 ms 22120 KB
sub1_70.txt 483 ms 22428 KB
sub1_71.txt 56 ms 14336 KB
sub1_72.txt 51 ms 14280 KB
sub1_73.txt 54 ms 14464 KB
sub1_74.txt 214 ms 26520 KB
sub1_75.txt 93 ms 17336 KB
sub1_76.txt 507 ms 49876 KB
sub1_77.txt 56 ms 14480 KB
sub1_78.txt 57 ms 14464 KB
sub1_79.txt 60 ms 14404 KB
sub1_80.txt 60 ms 14512 KB
sub1_81.txt 64 ms 14684 KB
sub1_82.txt 64 ms 14520 KB
sub1_83.txt 54 ms 14416 KB
sub1_84.txt 60 ms 14636 KB
sub1_85.txt 68 ms 14636 KB
sub1_86.txt 51 ms 14432 KB
sub1_87.txt 54 ms 14332 KB
sub1_88.txt 55 ms 14436 KB
sub1_89.txt 2183 ms 49980 KB
sub1_90.txt 2399 ms 49660 KB
sub1_91.txt 2231 ms 49952 KB
sub1_92.txt 2215 ms 50112 KB
sub1_93.txt 2196 ms 49788 KB
sub1_94.txt 54 ms 14264 KB