結果

問題 No.1576 織姫と彦星
ユーザー 小野寺健小野寺健
提出日時 2021-10-31 15:50:46
言語 Ruby
(3.3.0)
結果
AC  
実行時間 260 ms / 2,000 ms
コード長 1,135 bytes
コンパイル時間 31 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 12,288 KB
最終ジャッジ日時 2024-04-17 08:40:22
合計ジャッジ時間 10,234 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 80 ms
12,288 KB
testcase_01 AC 79 ms
12,288 KB
testcase_02 AC 81 ms
12,288 KB
testcase_03 AC 84 ms
12,160 KB
testcase_04 AC 82 ms
12,160 KB
testcase_05 AC 82 ms
12,160 KB
testcase_06 AC 81 ms
12,160 KB
testcase_07 AC 121 ms
12,160 KB
testcase_08 AC 108 ms
12,160 KB
testcase_09 AC 80 ms
12,288 KB
testcase_10 AC 183 ms
12,288 KB
testcase_11 AC 80 ms
12,160 KB
testcase_12 AC 151 ms
12,160 KB
testcase_13 AC 214 ms
12,288 KB
testcase_14 AC 173 ms
12,288 KB
testcase_15 AC 172 ms
12,160 KB
testcase_16 AC 204 ms
12,160 KB
testcase_17 AC 171 ms
12,160 KB
testcase_18 AC 97 ms
12,160 KB
testcase_19 AC 107 ms
12,160 KB
testcase_20 AC 175 ms
12,288 KB
testcase_21 AC 167 ms
12,160 KB
testcase_22 AC 183 ms
12,160 KB
testcase_23 AC 91 ms
12,288 KB
testcase_24 AC 94 ms
12,288 KB
testcase_25 AC 210 ms
12,160 KB
testcase_26 AC 118 ms
12,160 KB
testcase_27 AC 86 ms
12,160 KB
testcase_28 AC 187 ms
12,288 KB
testcase_29 AC 116 ms
12,160 KB
testcase_30 AC 83 ms
12,288 KB
testcase_31 AC 124 ms
12,160 KB
testcase_32 AC 174 ms
12,160 KB
testcase_33 AC 242 ms
12,160 KB
testcase_34 AC 79 ms
12,160 KB
testcase_35 AC 128 ms
12,160 KB
testcase_36 AC 91 ms
12,288 KB
testcase_37 AC 260 ms
12,160 KB
testcase_38 AC 189 ms
12,288 KB
testcase_39 AC 144 ms
12,288 KB
testcase_40 AC 121 ms
12,160 KB
testcase_41 AC 130 ms
12,160 KB
testcase_42 AC 83 ms
12,032 KB
testcase_43 AC 93 ms
12,160 KB
testcase_44 AC 235 ms
12,288 KB
testcase_45 AC 122 ms
12,160 KB
testcase_46 AC 179 ms
12,160 KB
testcase_47 AC 97 ms
12,160 KB
testcase_48 AC 137 ms
12,288 KB
testcase_49 AC 134 ms
12,160 KB
testcase_50 AC 86 ms
12,288 KB
testcase_51 AC 96 ms
12,288 KB
testcase_52 AC 247 ms
12,288 KB
testcase_53 AC 168 ms
12,160 KB
testcase_54 AC 197 ms
12,160 KB
testcase_55 AC 247 ms
12,288 KB
testcase_56 AC 245 ms
12,288 KB
testcase_57 AC 81 ms
12,160 KB
testcase_58 AC 107 ms
12,160 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:65: warning: ambiguous first argument; put parentheses or a space even after `-' operator
Syntax OK

ソースコード

diff # 

N = gets.to_i
s, e = gets.split(" ").map{|s| s.to_i}
stone = gets.split(" ").map{|s| s.to_i}

class UnionFind
	def initialize(n)
		@par = 0.upto(n-1).to_a
		@rank = Array.new(n, 0)
	end
	
	def unite(x, y)
		x = find(x)
		y = find(y)
		return if x == y
		if @rank[x] < @rank[y] then
			@par[x] = y
		else
			@par[y] = x
			@rank[x] += 1 if @rank[x] == @rank[y]
		end
	end
	
	def same?(x, y)
		find(x) == find(y)
	end
	
	private
	
	def find(x)
		if @par[x] == x then
			x
		else
			@par[x] = find(@par[x])
		end
	end
end

stone = [s] + stone + [e]

def getHaming(n)
	bit = 1
	haming = [n]
	32.times {
		haming << (n ^ bit)
		bit <<= 1
	}
	haming
end

uf = UnionFind.new(N+2)
v = Array.new(N+2) {Array.new}

stone.each_with_index {|x, i|
	haming = getHaming(x)
	(i+1).upto(N+1) {|j|
		if haming.include?(stone[j]) then
			uf.unite(i, j) 
			v[i] << j
			v[j] << i
		end
	}
}

if not uf.same?(0, N+1) then
	puts -1
else
	d = Array.new(N+2, Float::INFINITY)
	d[0] = 0
	q = [[0, 0]]
	while q.length > 0 do
		cv, c = q.shift
		v[cv].each {|nv|
			if d[nv] > c + 1 then
				d[nv] = c + 1
				q << [nv, c + 1]
			end
		}
	end
	puts d[N+1]-1
end
0