結果

問題 No.1094 木登り / Climbing tree
ユーザー TANIGUCHI KousukeTANIGUCHI Kousuke
提出日時 2021-03-10 09:06:33
言語 Ruby
(3.3.0)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,910 bytes
コンパイル時間 280 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 81,536 KB
最終ジャッジ日時 2024-10-12 00:30:56
合計ジャッジ時間 7,823 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 93 ms
17,536 KB
testcase_01 TLE -
testcase_02 AC 913 ms
58,112 KB
testcase_03 AC 666 ms
15,616 KB
testcase_04 AC 859 ms
40,832 KB
testcase_05 AC 1,427 ms
60,800 KB
testcase_06 AC 1,476 ms
33,024 KB
testcase_07 TLE -
testcase_08 TLE -
testcase_09 TLE -
testcase_10 TLE -
testcase_11 TLE -
testcase_12 TLE -
testcase_13 TLE -
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)
    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 = @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