結果

問題 No.1639 最小通信路
ユーザー face4face4
提出日時 2021-08-06 22:44:22
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 529 ms / 2,000 ms
コード長 852 bytes
コンパイル時間 15,633 ms
コンパイル使用メモリ 440,956 KB
実行使用メモリ 62,308 KB
最終ジャッジ日時 2023-10-17 04:14:02
合計ジャッジ時間 31,532 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 308 ms
54,764 KB
testcase_01 AC 312 ms
54,768 KB
testcase_02 AC 341 ms
55,020 KB
testcase_03 AC 371 ms
55,044 KB
testcase_04 AC 529 ms
62,308 KB
testcase_05 AC 316 ms
54,852 KB
testcase_06 AC 321 ms
54,888 KB
testcase_07 AC 305 ms
54,760 KB
testcase_08 AC 333 ms
54,992 KB
testcase_09 AC 310 ms
54,832 KB
testcase_10 AC 314 ms
54,848 KB
testcase_11 AC 318 ms
54,868 KB
testcase_12 AC 314 ms
54,848 KB
testcase_13 AC 321 ms
54,904 KB
testcase_14 AC 299 ms
54,764 KB
testcase_15 AC 310 ms
54,848 KB
testcase_16 AC 324 ms
54,932 KB
testcase_17 AC 324 ms
54,928 KB
testcase_18 AC 319 ms
54,808 KB
testcase_19 AC 318 ms
54,880 KB
testcase_20 AC 329 ms
55,016 KB
testcase_21 AC 305 ms
54,752 KB
testcase_22 AC 313 ms
54,828 KB
testcase_23 AC 317 ms
54,864 KB
testcase_24 AC 311 ms
54,848 KB
testcase_25 AC 324 ms
54,888 KB
testcase_26 AC 312 ms
54,824 KB
testcase_27 AC 309 ms
54,812 KB
testcase_28 AC 312 ms
54,792 KB
testcase_29 AC 328 ms
54,956 KB
testcase_30 AC 351 ms
55,032 KB
testcase_31 AC 316 ms
54,892 KB
testcase_32 AC 334 ms
54,988 KB
testcase_33 AC 315 ms
54,888 KB
testcase_34 AC 335 ms
55,016 KB
testcase_35 AC 367 ms
55,164 KB
testcase_36 AC 362 ms
55,056 KB
testcase_37 AC 344 ms
55,040 KB
testcase_38 AC 305 ms
54,812 KB
testcase_39 AC 329 ms
54,940 KB
testcase_40 AC 312 ms
54,828 KB
testcase_41 AC 315 ms
54,884 KB
testcase_42 AC 351 ms
55,028 KB
testcase_43 AC 317 ms
54,840 KB
testcase_44 AC 307 ms
54,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import kotlin.system.exitProcess

class UnionFind(val n: Int) {
    val p = MutableList(n) { it }

    fun parent(x: Int): Int {
        if (p[x] != x) {
            p[x] = parent(p[x])
        }
        return p[x]
    }

    fun unite(x: Int, y: Int) {
        val px = parent(x)
        val py = parent(y)
        p[px] = py
    }

    fun same(x: Int, y: Int): Boolean {
        return parent(x) == parent(y)
    }
}

fun main() {
    val n = readLine()!!.toInt()
    val uf = UnionFind(n)
    var edges = 0
    repeat(n * (n - 1) / 2) {
        val line = readLine()!!.split(" ")
        val (a, b) = line.subList(0, 2).map { it.toInt() - 1 }
        if (!uf.same(a, b)) {
            uf.unite(a, b)
            edges++
            if (edges == n - 1) {
                print(line[2])
                exitProcess(0)
            }
        }
    }
}
0