結果

問題 No.3056 Disconnected Coloring
コンテスト
ユーザー magurofly
提出日時 2025-03-14 21:35:44
言語 Ruby
(3.4.1)
結果
WA  
実行時間 -
コード長 1,052 bytes
コンパイル時間 228 ms
コンパイル使用メモリ 8,064 KB
実行使用メモリ 69,376 KB
最終ジャッジ日時 2025-03-14 21:36:23
合計ジャッジ時間 29,351 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 23 WA * 11
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:4: warning: ambiguous first argument; put parentheses or a space even after `-` operator
Main.rb:29: warning: ambiguous first argument; put parentheses or a space even after `-` operator
Main.rb:70: 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)
	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)
	graph[u].each do |v, _|
		next if dist_rev[v] <= dist_rev[u] + 1
		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] != dist_rev[0] - 1
	coloring[e] = ?B
	blue += 1
end
graph[N - 1].each do |v, e|
	next if dist[v] != dist[N - 1] - 1
	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