結果
問題 | No.1390 Get together |
ユーザー |
![]() |
提出日時 | 2021-02-12 23:36:49 |
言語 | Kotlin (2.1.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,075 bytes |
コンパイル時間 | 17,646 ms |
コンパイル使用メモリ | 452,080 KB |
実行使用メモリ | 102,548 KB |
最終ジャッジ日時 | 2024-07-20 01:26:58 |
合計ジャッジ時間 | 26,337 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 13 TLE * 1 -- * 15 |
ソースコード
import java.util.*fun main() {// val sc = Scanner(System.`in`)// val n = sc.nextInt()// val m = sc.nextInt()// val slimes = List(n) { Pair(sc.nextInt() - 1, sc.nextInt() - 1) }val (n, m) = readLine()!!.split(" ").map { it.toInt() }val slimes = mutableListOf<Pair<Int, Int>>()for (i in 0 until n) {val (b, c) = readLine()!!.split(" ").map { it.toInt() }slimes.add(Pair(b - 1, c - 1))}val dsu = DSU(m)val color_leaders = MutableList(n) { -1 }for ((box, color) in slimes) {if (color_leaders[color] == -1) {color_leaders[color] = box} else {dsu.merge(box, color_leaders[color])}}val seen = mutableListOf<Int>()var ans = 0for (i in 0 until m) {if (seen.contains(dsu.leader(i))) {continue}ans += dsu.size(i) - 1seen.add(dsu.leader(i))}println(ans)}fun eprintln(obj: Any) = System.err.println(obj.toString())/*** Disjoint set union.** convert from [AtCoderLibraryForJava - DSU](https://github.com/NASU41/AtCoderLibraryForJava/blob/8b3a3b599790a9ca8c7dd92e036af4ddc5be1b05/DSU/DSU.java)*/class DSU(private val n: Int) {private val parentOrSize: IntArray = IntArray(n) { -1 }/*** Merge nodes.*/fun merge(a: Int, b: Int): Int {if (a !in 0 until n) throw IndexOutOfBoundsException("a=$a")if (b !in 0 until n) throw IndexOutOfBoundsException("b=$b")var x = leader(a)var y = leader(b)if (x == y) return xif (-parentOrSize[x] < -parentOrSize[y]) {val tmp = xx = yy = tmp}parentOrSize[x] += parentOrSize[y]parentOrSize[y] = xreturn x}/*** True if two nodes are connected.*/fun same(a: Int, b: Int): Boolean {if (a !in 0 until n) throw IndexOutOfBoundsException("a=$a")if (b !in 0 until n) throw IndexOutOfBoundsException("b=$b")return leader(a) == leader(b)}/*** Get its leader node.*/fun leader(a: Int): Int {return if (parentOrSize[a] < 0) {a} else {parentOrSize[a] = leader(parentOrSize[a])parentOrSize[a]}}/*** A group's size.*/fun size(a: Int): Int {if (a !in 0 until n) throw IndexOutOfBoundsException("" + a)return -parentOrSize[leader(a)]}/*** Group by leader.*/fun groups(): ArrayList<ArrayList<Int>> {val leaderBuf = IntArray(n)val groupSize = IntArray(n)for (i in 0 until n) {leaderBuf[i] = leader(i)groupSize[leaderBuf[i]]++}val result = ArrayList<ArrayList<Int>>(n)for (i in 0 until n) {result.add(ArrayList(groupSize[i]))}for (i in 0 until n) {result[leaderBuf[i]].add(i)}result.removeIf { it.isEmpty() }return result}}