結果

問題 No.3056 Disconnected Coloring
ユーザー magurofly
提出日時 2025-03-14 21:53:58
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,030 bytes
コンパイル時間 457 ms
コンパイル使用メモリ 8,192 KB
実行使用メモリ 68,224 KB
最終ジャッジ日時 2025-03-14 21:54:33
合計ジャッジ時間 26,535 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 26 WA * 8
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:4: warning: ambiguous first argument; put parentheses or a space even after `-` operator
Main.rb:30: warning: ambiguous first argument; put parentheses or a space even after `-` operator
Main.rb:72: warning: ambiguous first argument; put parentheses or a space even after `-` operator
Syntax OK

ソースコード

diff # 

N, M = gets.split.map(&:to_i)

if M.odd?
	puts -1
	exit
end

edges = Array.new(M) { gets.split.map { _1.to_i - 1 } }

graph = Array.new(N) { [] }
M.times do |i|
	u, v = edges[i]
	graph[u] << [v, i]
	graph[v] << [u, i]
end

dist = [10**9] * N
dist[0] = 0
queue = [0]
while (u = queue.shift)
	next if u == N - 1
	graph[u].each do |v, _|
		next if dist[v] <= dist[u] + 1
		dist[v] = dist[u] + 1
		queue << v
	end
end

if dist[N - 1] <= 1
	puts -1
	exit
end


dist_rev = [10**9] * N
dist_rev[N - 1] = 0
queue = [N - 1]
while (u = queue.shift)
	next if u == 0
	graph[u].each do |v, _|
		next if 
		dist_rev[v] = dist_rev[u] + 1
		queue << v
	end
end

red = 0
blue = 0
coloring = [nil] * M
graph[0].each do |v, e|
	next if dist_rev[v] >= N
	coloring[e] = ?B
	blue += 1
end
graph[N - 1].each do |v, e|
	next if dist[v] >= N
	coloring[e] = ?R
	red += 1
end
M.times do |e|
	next if coloring[e]
	if red < blue
		coloring[e] = ?R
		red += 1
	else
		coloring[e] = ?B
		blue += 1
	end
end

if red != blue
	puts -1
	exit
end

puts coloring.join
0