結果

問題 No.3056 Disconnected Coloring
ユーザー magurofly
提出日時 2025-03-14 21:29:32
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 767 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 8,064 KB
実行使用メモリ 67,072 KB
最終ジャッジ日時 2025-03-14 21:29:57
合計ジャッジ時間 10,064 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 18 WA * 2 TLE * 4 -- * 10
権限があれば一括ダウンロードができます
コンパイルメッセージ
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:56: 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]
		dist[v] = dist[u] + 1
		queue << v
	end
end

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

red = 0
blue = 0
coloring = [nil] * M
graph[0].each do |v, e|
	coloring[e] = ?B
	blue += 1
end
graph[N - 1].each do |v, e|
	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