結果

問題 No.1390 Get together
ユーザー masashi0217masashi0217
提出日時 2021-03-26 01:59:41
言語 Ruby
(3.3.0)
結果
AC  
実行時間 709 ms / 2,000 ms
コード長 3,190 bytes
コンパイル時間 57 ms
コンパイル使用メモリ 11,540 KB
実行使用メモリ 31,292 KB
最終ジャッジ日時 2023-08-18 07:47:06
合計ジャッジ時間 14,073 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 74 ms
15,076 KB
testcase_01 AC 72 ms
15,120 KB
testcase_02 AC 77 ms
15,220 KB
testcase_03 AC 82 ms
15,652 KB
testcase_04 AC 80 ms
15,220 KB
testcase_05 AC 82 ms
15,372 KB
testcase_06 AC 82 ms
15,512 KB
testcase_07 AC 81 ms
15,384 KB
testcase_08 AC 79 ms
15,444 KB
testcase_09 AC 82 ms
15,476 KB
testcase_10 AC 70 ms
15,028 KB
testcase_11 AC 74 ms
15,244 KB
testcase_12 AC 76 ms
15,148 KB
testcase_13 AC 72 ms
15,164 KB
testcase_14 AC 76 ms
15,080 KB
testcase_15 AC 74 ms
15,304 KB
testcase_16 AC 484 ms
21,636 KB
testcase_17 AC 598 ms
31,080 KB
testcase_18 AC 517 ms
21,688 KB
testcase_19 AC 643 ms
31,292 KB
testcase_20 AC 651 ms
31,112 KB
testcase_21 AC 606 ms
31,200 KB
testcase_22 AC 605 ms
28,624 KB
testcase_23 AC 604 ms
28,708 KB
testcase_24 AC 603 ms
28,504 KB
testcase_25 AC 640 ms
31,008 KB
testcase_26 AC 678 ms
31,292 KB
testcase_27 AC 674 ms
31,200 KB
testcase_28 AC 663 ms
31,224 KB
testcase_29 AC 704 ms
31,228 KB
testcase_30 AC 709 ms
30,908 KB
testcase_31 AC 686 ms
31,084 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