Submission #45108485

Source Code Expand

(N,),*XY = $<.map{|ln| ln.split.map(&:to_i) }

X2Y = XY.group_by{|x,|x}.transform_values{|xys| xys.map{_2}.sort }
Y2X = XY.group_by{_2}.transform_values{|xys| xys.map{|x,|x}.sort }

X = X2Y.keys.sort
IX = X.each_with_index.to_h
XG = [-1]*X.size
F = lambda{|a|
	XG[a]<0 ? a : XG[a] = F[XG[a]]
}
U = lambda{|a,b|
	a,b = F[a],F[b]
	next if a==b
	a,b = b,a if XG[b]<XG[a]
	XG[a] += XG[b]
	XG[b] = a
}
Y2X.values.each{|x0,*xs|
	i0 = IX[x0]
	xs.each{|x| U[i0,IX[x]] }
}

GY = Array.new(X.size){ Hash.new 0 }
X2Y.each{|x,ys|
	gys = GY[F[IX[x]]]
	ys.each{|y| gys[y] += 1 }
}

p XG.zip(GY).sum{|xz,ys|
	0<=xz ? 0 : (-xz)*ys.size-ys.values.sum
}

Submission Info

Submission Time
Task F - Must Be Rectangular!
User ds14050
Language Ruby (2.7.1)
Score 600
Code Size 668 Byte
Status AC
Exec Time 341 ms
Memory 47164 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 20
Set Name Test Cases
Sample s1.txt, s2.txt, s3.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt AC 56 ms 14128 KiB
02.txt AC 56 ms 14104 KiB
03.txt AC 54 ms 14208 KiB
04.txt AC 51 ms 14132 KiB
05.txt AC 56 ms 14180 KiB
06.txt AC 59 ms 14356 KiB
07.txt AC 59 ms 14104 KiB
08.txt AC 58 ms 14388 KiB
09.txt AC 332 ms 43664 KiB
10.txt AC 335 ms 45960 KiB
11.txt AC 337 ms 46008 KiB
12.txt AC 336 ms 44900 KiB
13.txt AC 341 ms 45936 KiB
14.txt AC 334 ms 46032 KiB
15.txt AC 337 ms 46008 KiB
16.txt AC 339 ms 47164 KiB
17.txt AC 226 ms 31408 KiB
s1.txt AC 55 ms 14096 KiB
s2.txt AC 55 ms 14052 KiB
s3.txt AC 56 ms 14172 KiB