結果

問題 No.1390 Get together
ユーザー masashi0217masashi0217
提出日時 2021-03-26 01:50:16
言語 Ruby
(3.3.0)
結果
RE  
実行時間 -
コード長 3,190 bytes
コンパイル時間 99 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 30,592 KB
最終ジャッジ日時 2024-11-27 11:25:26
合計ジャッジ時間 12,247 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 88 ms
12,032 KB
testcase_01 AC 77 ms
12,160 KB
testcase_02 AC 76 ms
12,288 KB
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 AC 76 ms
12,032 KB
testcase_11 AC 78 ms
12,160 KB
testcase_12 AC 79 ms
12,032 KB
testcase_13 RE -
testcase_14 AC 76 ms
12,032 KB
testcase_15 AC 77 ms
12,160 KB
testcase_16 AC 496 ms
19,328 KB
testcase_17 AC 569 ms
29,696 KB
testcase_18 AC 499 ms
19,456 KB
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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[ponit] += 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[ponit_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