結果

問題 No.2290 UnUnion Find
ユーザー simansiman
提出日時 2023-05-07 21:59:15
言語 Ruby
(3.3.0)
結果
AC  
実行時間 569 ms / 2,000 ms
コード長 998 bytes
コンパイル時間 41 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 17,792 KB
最終ジャッジ日時 2024-11-24 20:37:10
合計ジャッジ時間 28,895 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
12,288 KB
testcase_01 AC 75 ms
12,288 KB
testcase_02 AC 478 ms
12,416 KB
testcase_03 AC 528 ms
15,104 KB
testcase_04 AC 532 ms
14,976 KB
testcase_05 AC 526 ms
14,976 KB
testcase_06 AC 521 ms
14,976 KB
testcase_07 AC 543 ms
14,976 KB
testcase_08 AC 539 ms
14,848 KB
testcase_09 AC 546 ms
14,848 KB
testcase_10 AC 532 ms
14,976 KB
testcase_11 AC 539 ms
14,848 KB
testcase_12 AC 542 ms
14,976 KB
testcase_13 AC 542 ms
14,848 KB
testcase_14 AC 539 ms
14,848 KB
testcase_15 AC 544 ms
14,976 KB
testcase_16 AC 532 ms
14,848 KB
testcase_17 AC 535 ms
14,848 KB
testcase_18 AC 547 ms
14,848 KB
testcase_19 AC 536 ms
15,232 KB
testcase_20 AC 557 ms
17,792 KB
testcase_21 AC 487 ms
12,288 KB
testcase_22 AC 519 ms
13,568 KB
testcase_23 AC 517 ms
13,440 KB
testcase_24 AC 552 ms
15,744 KB
testcase_25 AC 510 ms
12,928 KB
testcase_26 AC 565 ms
17,152 KB
testcase_27 AC 560 ms
16,768 KB
testcase_28 AC 526 ms
14,464 KB
testcase_29 AC 552 ms
15,488 KB
testcase_30 AC 508 ms
12,544 KB
testcase_31 AC 540 ms
15,360 KB
testcase_32 AC 515 ms
13,184 KB
testcase_33 AC 533 ms
14,592 KB
testcase_34 AC 567 ms
17,664 KB
testcase_35 AC 569 ms
17,152 KB
testcase_36 AC 506 ms
13,312 KB
testcase_37 AC 532 ms
13,952 KB
testcase_38 AC 525 ms
13,184 KB
testcase_39 AC 531 ms
13,696 KB
testcase_40 AC 564 ms
16,896 KB
testcase_41 AC 521 ms
12,928 KB
testcase_42 AC 549 ms
15,104 KB
testcase_43 AC 545 ms
15,104 KB
testcase_44 AC 560 ms
14,976 KB
testcase_45 AC 557 ms
14,848 KB
testcase_46 AC 560 ms
14,976 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:66: warning: ambiguous first argument; put parentheses or a space even after `-' operator
Syntax OK

ソースコード

diff # 

class UnionFind
  def initialize(n)
    @size = Array.new(n, 1)
    @rank = Array.new(n, 0)
    @parent = []

    (0..n).each do |i|
      @parent[i] = i
    end
  end

  def find(x)
    if @parent[x] == x
      x
    else
      @parent[x] = find(@parent[x])
    end
  end

  def unite(x, y)
    x = find(x)
    y = find(y)
    return if x == y

    if x > y
      @parent[x] = y
      @size[y] += @size[x]
    else
      @parent[y] = x
      @size[x] += @size[y]

      @rank[x] += 1 if @rank[x] == @rank[y]
    end
  end

  def same?(x, y)
    find(x) == find(y)
  end

  def size(x)
    @size[find(x)]
  end
end

N, Q = gets.split.map(&:to_i)
uf = UnionFind.new(N + 1)
cur = 2

Q.times do
  q = gets.split.map(&:to_i)

  case q[0]
  when 1
    u, v = q[1..2].sort
    uf.unite(u, v)

    while uf.find(cur) == 1 && cur <= N
      cur += 1
    end
  when 2
    v = q[1]

    par = uf.find(v)

    if cur > N
      puts -1
    elsif par != 1
      puts 1
    else
      puts cur
    end
  end
end
0