結果

問題 No.1094 木登り / Climbing tree
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2021-03-09 20:59:22
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 1,837 bytes
コンパイル時間 143 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 78,748 KB
最終ジャッジ日時 2024-04-19 21:15:32
合計ジャッジ時間 7,258 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
19,100 KB
testcase_01 TLE -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class LCA
  class << self
    def create(g, s = 0)
      parent = Array.new(g.size)
      active = Array.new(g.size, 0)
      depth = Array.new(g.size)
      tour = []
      
      u = parent[s] = s
      depth[s] = 0
      tour << s
      
      while true
        if (j = active[u]) >= g[u].size
          break if u == s
          u = parent[u]
          tour << u
          active[u] += 1
        else
          v, d = g[u][j]
          if !parent[v]
            parent[v] = u
            depth[v] = depth[u] + d
            u = v
            tour << u
          else
            active[u] += 1
          end
        end
      end
      new(tour, depth)
    end
  end

  def initialize(tour, depth)
    @tour = tour
    @depth = depth

    @ord = Array.new(depth.size)
    @offset = 1 << @tour.size.bit_length
    @data = Array.new(@offset << 1, -1)

    build!
  end

  def dist(a,b)
    c = lca(a,b)
    @depth[a] + @depth[b] - 2 * @depth[c]
  end

  def lca(a,b)
    a,b = b,a if @ord[b] < @ord[a]
    find_min(@ord[a], @ord[b] + 1)
  end
  private
  
  def find_min(a, b, k = 1, l = 0, r = @offset)
    return -1 if b <= l || r <= a
    return @data[k] if a <= l && r <= b
    mid = (l + r) / 2
    return min_depth(find_min(a, b, 2 * k, l, mid), find_min(a, b, 2 * k + 1, mid, r))
  end

  def min_depth(a,b)
    a < 0 ? b :
    b < 0 ? a :
    @depth[a] < @depth[b] ? a : b
  end

  def build!
    @tour.each_with_index do |u, i| 
      @data[@offset + i] = u
      @ord[u] = i if !@ord[u]
    end
    k = @offset
    @data[k] = min_depth(@data[2 * k], @data[2 * k + 1]) while (k -= 1) > 0
  end
  
end

N = gets.to_i
G = Array.new(N + 1){ [] }
(N - 1).times do
  u, v, d = gets.split.map(&:to_i)
  G[u] << [v, d]
  G[v] << [u, d]
end

lca = LCA.create(G, 1)

Q = gets.to_i
puts Q.times.map{ lca.dist(*gets.split.map(&:to_i)) }
0