結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 78 ms
12,160 KB
testcase_01 AC 78 ms
12,288 KB
testcase_02 AC 510 ms
12,544 KB
testcase_03 AC 532 ms
14,848 KB
testcase_04 AC 556 ms
14,848 KB
testcase_05 AC 568 ms
14,976 KB
testcase_06 AC 571 ms
14,848 KB
testcase_07 AC 538 ms
15,104 KB
testcase_08 AC 540 ms
14,848 KB
testcase_09 AC 547 ms
14,976 KB
testcase_10 AC 525 ms
14,720 KB
testcase_11 AC 569 ms
14,848 KB
testcase_12 AC 548 ms
15,104 KB
testcase_13 AC 531 ms
14,720 KB
testcase_14 AC 539 ms
14,848 KB
testcase_15 AC 556 ms
14,976 KB
testcase_16 AC 586 ms
14,976 KB
testcase_17 AC 560 ms
14,848 KB
testcase_18 AC 571 ms
14,976 KB
testcase_19 AC 545 ms
15,232 KB
testcase_20 AC 563 ms
17,664 KB
testcase_21 AC 487 ms
12,288 KB
testcase_22 AC 522 ms
13,184 KB
testcase_23 AC 524 ms
13,440 KB
testcase_24 AC 554 ms
15,616 KB
testcase_25 AC 521 ms
13,184 KB
testcase_26 AC 559 ms
17,024 KB
testcase_27 AC 551 ms
16,768 KB
testcase_28 AC 535 ms
14,592 KB
testcase_29 AC 551 ms
15,488 KB
testcase_30 AC 561 ms
12,544 KB
testcase_31 AC 545 ms
15,232 KB
testcase_32 AC 549 ms
13,184 KB
testcase_33 AC 558 ms
14,464 KB
testcase_34 AC 604 ms
17,792 KB
testcase_35 AC 567 ms
17,024 KB
testcase_36 AC 540 ms
13,184 KB
testcase_37 AC 542 ms
13,952 KB
testcase_38 AC 545 ms
12,928 KB
testcase_39 AC 527 ms
13,824 KB
testcase_40 AC 573 ms
16,896 KB
testcase_41 AC 527 ms
13,056 KB
testcase_42 AC 558 ms
14,976 KB
testcase_43 AC 564 ms
15,104 KB
testcase_44 AC 534 ms
14,720 KB
testcase_45 AC 553 ms
14,848 KB
testcase_46 AC 565 ms
14,848 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