Submission #2832990


Source Code Expand

Copy
class UnionFind
  attr :id, :rank

  def initialize(n)
    @id   = (0..n).to_a
    @rank = Array.new(n,0)
  end

  def root(i)
    if @id[i] == i or i == @id[@id[i]]
      i
    else
      @id[i] = root(@id[i])
      @id[i]
    end
  end

  # find, check if p and q has the same root
  def same?(p, q)
    root(p) == root(q)
  end

  # union, to merge components containing p and q
  # set id of p's root to the id of q's root
  def unite(p, q)

    i = root(p)
    j = root(q)

    return if i == j

    if @rank[i] < @rank[j]
      @id[i] = j
    else
      @id[j] = i;
      @rank[i]+=1  if @rank[i] == @rank[j]
    end
  end
end

def get_hash_key(a, b)
  a << 32 | b
end

lines = $stdin.read

array = lines.split("\n")
N,K,L = array[0].split(" ").map(&:to_i)

ufpq = UnionFind.new(N+1)
ufrs = UnionFind.new(N+1)

array[1..K].each do |str|
  pi,qi = str.split(" ").map(&:to_i)
  ufpq.unite(pi,qi)
end

array[K+1..K+L+1].each do |str|
  ri,si = str.split(" ").map(&:to_i)
  ufrs.unite(ri,si)
end

m = {}

(1..N).each do |n|
  rpq = ufpq.root(n)
  rrs = ufrs.root(n)
  key = get_hash_key(rpq,rrs)
  if m.has_key?(key)
    m[key] += 1
  else
    m[key] = 1
  end
end

(1..N).each do |n|
  rpq = ufpq.root(n)
  rrs = ufrs.root(n)
  key = get_hash_key(rpq,rrs)
  puts m[key]
end

Submission Info

Submission Time
Task D - 連結 / Connectivity
User hiroyuking
Language Ruby (2.3.3)
Score 400
Code Size 1356 Byte
Status
Exec Time 767 ms
Memory 36788 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt
All 400 / 400 subtask0_0.txt, subtask0_1.txt, subtask0_2.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt
Case Name Status Exec Time Memory
subtask0_0.txt 7 ms 1788 KB
subtask0_1.txt 7 ms 1788 KB
subtask0_2.txt 7 ms 1788 KB
subtask1_0.txt 334 ms 17916 KB
subtask1_1.txt 662 ms 36348 KB
subtask1_10.txt 328 ms 18172 KB
subtask1_11.txt 621 ms 34100 KB
subtask1_12.txt 704 ms 33660 KB
subtask1_13.txt 704 ms 35764 KB
subtask1_14.txt 697 ms 31868 KB
subtask1_2.txt 621 ms 29876 KB
subtask1_3.txt 767 ms 35764 KB
subtask1_4.txt 704 ms 32124 KB
subtask1_5.txt 328 ms 18172 KB
subtask1_6.txt 599 ms 33020 KB
subtask1_7.txt 719 ms 35320 KB
subtask1_8.txt 753 ms 36788 KB
subtask1_9.txt 678 ms 28664 KB