結果
問題 |
No.1950 片道きゃっちぼーる
|
ユーザー |
![]() |
提出日時 | 2022-05-20 22:24:04 |
言語 | Crystal (1.14.0) |
結果 |
AC
|
実行時間 | 290 ms / 3,000 ms |
コード長 | 1,452 bytes |
コンパイル時間 | 12,215 ms |
コンパイル使用メモリ | 296,576 KB |
実行使用メモリ | 55,664 KB |
最終ジャッジ日時 | 2024-09-20 08:38:52 |
合計ジャッジ時間 | 18,147 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 23 |
ソースコード
n = read_line.to_i x = read_line.split.map(&.to_i) a = read_line.split.map(&.to_i) g = Array.new(n) { [] of Int32 } g_rev = Array.new(n) { [] of Int32 } pos = Hash(Int32, Int32).new n.times do |i| pos[x[i]] = i end n.times do |i| if pos.has_key?(x[i] - a[i]) g_rev[pos[x[i] - a[i]]] << i g[i] << pos[x[i] - a[i]] end if pos.has_key?(x[i] + a[i]) g_rev[pos[x[i] + a[i]]] << i g[i] << pos[x[i] + a[i]] end end stack = [] of Int32 visited = Array.new(n, false) n.times do |i| scc_dfs(g, stack, visited, i) end visited.fill(false) groups = [] of Array(Int32) stack.reverse.each do |i| next if visited[i] group = [] of Int32 scc_dfs_rev(g_rev, group, visited, i) groups << group end def scc_dfs(g, stack, visited, cur) return if visited[cur] visited[cur] = true g[cur].each do |c| scc_dfs(g, stack, visited, c) end stack << cur end def scc_dfs_rev(g_rev, list, visited, cur) return if visited[cur] visited[cur] = true g_rev[cur].each do |c| scc_dfs_rev(g_rev, list, visited, c) end list << cur end ans = Array.new(n, 0) groups.reverse.each do |group| max = 0 group.each do |i| max = {max, x[i] + a[i]}.max if pos.has_key?(x[i] + a[i]) max = {max, ans[pos[x[i] + a[i]]]}.max end if pos.has_key?(x[i] - a[i]) max = {max, ans[pos[x[i] - a[i]]]}.max end end group.each do |i| ans[i] = max end end puts n.times.map { |i| ans[i] - x[i] }.join("\n")