Submission #55800705

Source Code Expand

H,W,Y,*A = $<.read.split.map(&:to_i)
G = [-1]*(H*W+1)
F = lambda{|a|
	G[a]<0 ? a : G[a] = F[G[a]]
}
U = lambda{|a,b|
	a,b = F[a],F[b]
	next if a==b
	a,b = b,a if G[b]<G[a]
	G[a] += G[b]
	G[b] = a
}
I = (H*W).times.sort_by{|i| A[i] }
puts (1..Y).map{|y|
	while I[0]&&A[I[0]]<=y
		i = I.shift
		a = A[i]
		h,w = i.divmod W
		[[h-1,w],[h+1,w],[h,w-1],[h,w+1]].each{|h,w|
			j = h*W+w
			if h<0 || H<=h || w<0 || W<=w
				U[i,H*W]
			elsif A[j]<=a
				U[i,j]
			end
		}
	end
	next H*W+1+G[F[H*W]]
}

Submission Info

Submission Time
Task E - Sinking Land
User ds14050
Language Ruby (ruby 3.2.2)
Score 450
Code Size 524 Byte
Status AC
Exec Time 1629 ms
Memory 130088 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 450 / 450
Status
AC × 2
AC × 46
Set Name Test Cases
Sample example_00.txt, example_01.txt
All example_00.txt, example_01.txt, hand_00.txt, hand_01.txt, hand_02.txt, hand_03.txt, hand_04.txt, hand_05.txt, hand_06.txt, hand_07.txt, hand_08.txt, hand_09.txt, hand_10.txt, hand_11.txt, hand_12.txt, hand_13.txt, random_00.txt, 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
Case Name Status Exec Time Memory
example_00.txt AC 41 ms 17376 KiB
example_01.txt AC 42 ms 17476 KiB
hand_00.txt AC 1297 ms 126248 KiB
hand_01.txt AC 1289 ms 126616 KiB
hand_02.txt AC 1180 ms 124560 KiB
hand_03.txt AC 91 ms 18456 KiB
hand_04.txt AC 91 ms 18504 KiB
hand_05.txt AC 84 ms 18476 KiB
hand_06.txt AC 1424 ms 129516 KiB
hand_07.txt AC 1607 ms 117628 KiB
hand_08.txt AC 385 ms 123064 KiB
hand_09.txt AC 1374 ms 130088 KiB
hand_10.txt AC 1492 ms 118228 KiB
hand_11.txt AC 42 ms 17244 KiB
hand_12.txt AC 327 ms 121180 KiB
hand_13.txt AC 42 ms 17272 KiB
random_00.txt AC 1472 ms 129300 KiB
random_01.txt AC 1461 ms 128984 KiB
random_02.txt AC 1442 ms 129672 KiB
random_03.txt AC 1432 ms 129264 KiB
random_04.txt AC 1426 ms 128664 KiB
random_05.txt AC 1584 ms 129684 KiB
random_06.txt AC 1629 ms 129676 KiB
random_07.txt AC 1401 ms 128664 KiB
random_08.txt AC 1404 ms 128044 KiB
random_09.txt AC 1403 ms 128704 KiB
random_10.txt AC 1368 ms 129272 KiB
random_11.txt AC 1412 ms 129420 KiB
random_12.txt AC 1367 ms 128068 KiB
random_13.txt AC 1373 ms 128544 KiB
random_14.txt AC 1370 ms 129184 KiB
random_15.txt AC 1337 ms 129176 KiB
random_16.txt AC 1325 ms 128008 KiB
random_17.txt AC 1367 ms 129344 KiB
random_18.txt AC 1321 ms 128780 KiB
random_19.txt AC 1328 ms 128460 KiB
random_20.txt AC 1426 ms 128592 KiB
random_21.txt AC 1399 ms 128444 KiB
random_22.txt AC 1403 ms 129272 KiB
random_23.txt AC 1406 ms 128928 KiB
random_24.txt AC 1444 ms 129592 KiB
random_25.txt AC 1410 ms 130008 KiB
random_26.txt AC 1499 ms 129644 KiB
random_27.txt AC 1419 ms 129740 KiB
random_28.txt AC 1345 ms 129796 KiB
random_29.txt AC 1346 ms 130076 KiB