結果

問題 No.1390 Get together
ユーザー masashi0217masashi0217
提出日時 2021-03-26 01:59:41
言語 Ruby
(3.3.0)
結果
AC  
実行時間 764 ms / 2,000 ms
コード長 3,190 bytes
コンパイル時間 310 ms
コンパイル使用メモリ 7,424 KB
実行使用メモリ 29,952 KB
最終ジャッジ日時 2024-05-05 13:40:39
合計ジャッジ時間 13,428 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 85 ms
12,160 KB
testcase_01 AC 76 ms
12,160 KB
testcase_02 AC 76 ms
12,160 KB
testcase_03 AC 89 ms
12,160 KB
testcase_04 AC 86 ms
12,416 KB
testcase_05 AC 87 ms
12,416 KB
testcase_06 AC 86 ms
12,416 KB
testcase_07 AC 85 ms
12,416 KB
testcase_08 AC 85 ms
12,288 KB
testcase_09 AC 89 ms
12,160 KB
testcase_10 AC 76 ms
12,160 KB
testcase_11 AC 74 ms
11,904 KB
testcase_12 AC 75 ms
12,160 KB
testcase_13 AC 74 ms
12,032 KB
testcase_14 AC 74 ms
12,160 KB
testcase_15 AC 75 ms
12,032 KB
testcase_16 AC 491 ms
19,456 KB
testcase_17 AC 564 ms
29,824 KB
testcase_18 AC 507 ms
19,456 KB
testcase_19 AC 633 ms
29,824 KB
testcase_20 AC 635 ms
29,952 KB
testcase_21 AC 621 ms
29,824 KB
testcase_22 AC 592 ms
26,496 KB
testcase_23 AC 590 ms
25,984 KB
testcase_24 AC 590 ms
26,240 KB
testcase_25 AC 628 ms
29,952 KB
testcase_26 AC 623 ms
29,952 KB
testcase_27 AC 677 ms
29,824 KB
testcase_28 AC 637 ms
29,824 KB
testcase_29 AC 612 ms
29,696 KB
testcase_30 AC 626 ms
29,952 KB
testcase_31 AC 764 ms
29,952 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

class Un
    def initialize(n)
        @size = Array.new(n,1)
        @mae = Array.new(n,-1)
        @rank = Array.new(n,0)
    end
    def find(n)
        ans = 0
        if @mae[n] == -1
             return n
        else
            ans = find(@mae[n])
            return ans
        end
    end
    def same(x,y)
        point = 0
        if @mae[x] == -1 && @mae[y] == -1
            point_1 = find(y)
            point_2 = find(x)
            if point_1 == point_2
                ok = true
                return ok
            end
        elsif @mae[x] == -1
            point = find(y)
            if point == x
                ok = true
                return ok
            end
        elsif @mae[y] == -1
            point = find(x)
            if point == y
                ok = true
                return ok
            end
        else
            point_1 = find(x)
            point_2 = find(y)
            if point_1 == point_2
                ok = true
                return ok
            end
        end
    end
    def union(x,y)
        point = 0
        if @mae[x] == -1 && @mae[y] == -1
            point_1 = find(x)
            point_2 = find(y)
            if @rank[point_1] < @rank[point_2]
                @size[point_2] += @size[point_1]
                @mae[point_1] = point_2 
            else
                # print "point_1" + " " + "#{point_1}" + "\n"
                # print "point_2" + " " + "#{point_2}" + "\n"
                @size[point_1] += @size[point_2]
                @mae[point_2] = point_1
                @rank[point_1] += 1 if @rank[point_1] == @rank[point_2]
            end
        elsif @mae[x] == -1
            point = find(y)
            if @rank[point] < @rank[x]
                @size[x] += @size[point]
                @mae[point] = x
            else
                @size[point] += @size[x]
                @mae[x] = point
                @rank[point] += 1 if @rank[point] == @rank[x]
            end
        elsif @mae[y] == -1
            point = find(x)
            if @rank[point] < @rank[y]
                @size[y] += @size[point]
                @mae[point] = y
            else
                @size[point] += @size[y]
                @mae[y] = point
                @rank[point] += 1 if @rank[point] == @rank[y]
            end
        else
            point_1 = find(x)
            point_2 = find(y)
            if @rank[point_1] < @rank[point_2]
                @size[point_2] += @size[point_1]
                @mae[point_1] = point_2 
            else
                @size[point_1] += @size[point_2]
                @mae[point_2] = point_1
                @rank[point_1] += 1 if @rank[point_1] == @rank[point_2]
            end
        end
        # p @rank
        # p @size
        # p @mae
    end
end

hash = Hash.new{|i,j| hash[j] = []}
n, m = gets.chomp.split(" ").map(&:to_i)
n.times do
    b, c = gets.chomp.split(" ").map(&:to_i)
    hash[c] << b
end
uf = Un.new(m)
count = 0
hash.each do |box,colors|
    # puts "-----"
    # p colors
    # puts "~~~~~~"
    colors.each_cons(2) do |i,j|
        tf = uf.same(i-1,j-1)
        next if tf
        count += 1
        uf.union(i-1,j-1)
    end
end
puts count
0