Submission #63548237

---

Source Code Expand

class WeightedUnionFind
  attr_accessor(:node, :val)

  def initialize(n)
    @node = Array.new(n, -1)
    @val = Array.new(n, 0)
  end

  def root(x)
    if @node[x] < 0
      return x
    else
      r = root(@node[x])
      @val[x] ^= @val[@node[x]]
      @node[x] = r
      return r
    end
  end

  def size(x)
    x = root(x)
    return (- @node[x])
  end

  def same?(x, y)
    return root(x) == root(y)
  end

  def weight(x)
    root(x)
    return @val[x]
  end

  def diff(x, y)
    return weight(y) ^ weight(x)
  end

  def unite(x, y, w)
    w ^= weight(x)
    w ^= weight(y)
    rx = root(x)
    ry = root(y)
    return if rx == ry
    
    dx = @node[rx]
    dy = @node[ry]
    if dx <= dy # xの方が大きい
      @node[ry] = rx
      @node[rx] += dy
      @val[ry] = w
    else
      @node[rx] = ry
      @node[ry] += dx
      @val[rx] = w
    end
  end
end

n, m = gets.chomp.split.map(&:to_i)
wuf = WeightedUnionFind.new(n)
m.times do
  xi, yi, zi = gets.chomp.split.map(&:to_i)
  xi -= 1
  yi -= 1
  if wuf.same?(xi, yi) && wuf.diff(xi, yi) != zi
    puts "-1"
    exit
  end

  wuf.unite(xi, yi, zi)
end

cnt = Hash.new
a = Array.new(n)
n.times do |v|
  r = wuf.root(v)
  if wuf.size(r) == 1
    a[v] = 0
    next
  end

  if cnt[r].nil?
    cnt[r] ||= Array.new(30) { Array.new(2, 0) }
  end

  w = wuf.diff(v, r)
  30.times do |d|
    cnt[r][d][(w >> d) & 1] += 1
  end
end

n.times do |v|
  r = wuf.root(v)
  next if wuf.size(r) == 1 || v != r

  a[r] = 0
  30.times do |d|
    if cnt[r][d][1] > cnt[r][d][0]
      bit = 1
    else
      bit = 0
    end
    a[v] |= (bit << d)
  end
end

n.times do |v|
  r = wuf.root(v)
  next if wuf.size(r) == 1 || v == r

  a[v] = wuf.diff(r, v) ^ a[r]
end

puts a.join(" ")

Submission Info

Judge Result