Submission #16962544

Source Code Expand

N = gets.to_i

X2N = [nil]*N
Y2N = [nil]*N
N2Y = [nil]*N
N.times{|n|
	x,y = gets.split.map{|_|_.to_i-1}
	X2N[x] = Y2N[y] = n
	N2Y[n] = y
}

G = [-1]*N
F = lambda{|n|
	next G[n] < 0 ? n : G[n] = F[G[n]]
}
U = lambda{|*nm|
	n,m = nm.map(&F)
	next if n == m
	n,m = m,n unless G[n] < G[m]
	G[n] += G[m]
	G[m] = n
}

Ys = []
X2N.each{|n|
	y = N2Y[n]
	i = Ys.bsearch_index{|_| _<y }
	if i
		ys = Ys.pop(Ys.size-i)
		ys.each{|y| U[n,Y2N[y]] }
		Ys << ys.pop
	else
		Ys << y
	end
}

puts G.map.with_index{|g,n| g < 0 ? -g : -G[F[n]]  }

Submission Info

Submission Time
Task A - Reachable Towns
User ds14050
Language Ruby (2.7.1)
Score 300
Code Size 565 Byte
Status AC
Exec Time 559 ms
Memory 22224 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 300 / 300
Status
AC × 2
AC × 24
Set Name Test Cases
Sample example_00, example_01
All example_00, example_01, manyperm_00, manyperm_01, manyperm_02, manyperm_03, max_random_00, max_random_01, random_00, random_01, small_00, small_01, small_02, small_03, small_04, small_05, small_06, small_07, small_08, small_09, special1_00, special1_01, special1_02, special1_03
Case Name Status Exec Time Memory
example_00 AC 63 ms 14120 KiB
example_01 AC 66 ms 14148 KiB
manyperm_00 AC 559 ms 22224 KiB
manyperm_01 AC 546 ms 22184 KiB
manyperm_02 AC 547 ms 22104 KiB
manyperm_03 AC 542 ms 22148 KiB
max_random_00 AC 483 ms 21920 KiB
max_random_01 AC 477 ms 21740 KiB
random_00 AC 327 ms 18924 KiB
random_01 AC 382 ms 19832 KiB
small_00 AC 61 ms 14136 KiB
small_01 AC 66 ms 14224 KiB
small_02 AC 66 ms 14116 KiB
small_03 AC 64 ms 14096 KiB
small_04 AC 66 ms 14144 KiB
small_05 AC 62 ms 14252 KiB
small_06 AC 65 ms 14024 KiB
small_07 AC 69 ms 14100 KiB
small_08 AC 60 ms 14076 KiB
small_09 AC 64 ms 14056 KiB
special1_00 AC 376 ms 20280 KiB
special1_01 AC 369 ms 19936 KiB
special1_02 AC 165 ms 16112 KiB
special1_03 AC 403 ms 20800 KiB