結果

問題 No.1094 木登り / Climbing tree
ユーザー TANIGUCHI Kousuke
提出日時 2021-03-10 09:11:30
言語 Ruby
(3.4.1)
結果
RE  
実行時間 -
コード長 1,900 bytes
コンパイル時間 305 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 59,008 KB
最終ジャッジ日時 2024-10-12 00:35:10
合計ジャッジ時間 24,137 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other RE * 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
    @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)
    x = -1
    l,r = @offset + a, @offset + b
    while l < r
      if l.odd?
        x = min_depth(x, @data[l]);
        l += l[0]
      end
      if r.odd?
        r -= r[0]; 
        x = min_depth(x, @data[r])
      end
      l >>= 1
      r >>= 1
    end
    return x
  end

  def min_depth(a,b)
    return b if a < 0
    return a if b < 0
    @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 = @data.size
    @data[k >> 1] = min_depth(@data[k >> 1], @data[k]) 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