結果

問題 No.1266 7 Colors
ユーザー rutilicusrutilicus
提出日時 2020-10-25 12:45:40
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,442 ms / 3,000 ms
コード長 2,865 bytes
コンパイル時間 18,633 ms
コンパイル使用メモリ 435,816 KB
実行使用メモリ 93,952 KB
最終ジャッジ日時 2023-09-29 02:05:13
合計ジャッジ時間 49,093 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 302 ms
52,936 KB
testcase_01 AC 304 ms
52,860 KB
testcase_02 AC 299 ms
52,856 KB
testcase_03 AC 1,254 ms
74,620 KB
testcase_04 AC 1,300 ms
81,608 KB
testcase_05 AC 1,313 ms
77,340 KB
testcase_06 AC 1,409 ms
84,780 KB
testcase_07 AC 1,442 ms
93,952 KB
testcase_08 AC 1,316 ms
82,792 KB
testcase_09 AC 1,340 ms
76,388 KB
testcase_10 AC 1,344 ms
81,496 KB
testcase_11 AC 1,337 ms
75,036 KB
testcase_12 AC 1,256 ms
75,068 KB
testcase_13 AC 1,284 ms
78,208 KB
testcase_14 AC 1,279 ms
74,344 KB
testcase_15 AC 1,396 ms
91,484 KB
testcase_16 AC 1,232 ms
76,340 KB
testcase_17 AC 1,319 ms
84,016 KB
testcase_18 AC 1,054 ms
92,744 KB
testcase_19 AC 1,165 ms
93,592 KB
testcase_20 AC 1,126 ms
93,672 KB
testcase_21 AC 886 ms
68,344 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:111:25: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
                builder.appendln(uf.sizeOf(x * 7))
                        ^

ソースコード

diff # 

class UnionFind(n: Int) {
    private val parent = IntArray(n) { -1 }
    private val rank = IntArray(n)
    private val size = IntArray(n) { 1 }
    private var numTree = n

    fun find(x: Int): Int {
        if (parent[x] == -1) {
            return x
        } else {
            parent[x] = find(parent[x])
            return parent[x]
        }
    }

    fun isSame(x: Int, y: Int): Boolean {
        return find(x) == find(y)
    }

    fun getSize(): Int {
        return numTree
    }

    fun sizeOf(x: Int): Int {
        return size[find(x)]
    }

    fun rankOf(x: Int): Int {
        return rank[find(x)]
    }

    fun unite(x: Int, y: Int) {
        val parentX = find(x)
        val parentY = find(y)

        if (parentX == parentY) {
            return
        }

        numTree--

        if (rank[parentX] < rank[parentY]) {
            parent[parentX] = parentY
            size[parentY] += size[parentX]
        } else {
            parent[parentY] = parentX
            size[parentX] += size[parentY]
            if (rank[parentX] == rank[parentY]) {
                rank[parentX]++
            }
        }
    }
}

fun main() {
    val builder = StringBuilder()

    // 解説読む、問題が読解できなかった

    val (n, m, q) = readInputLine().split(" ").map { it.toInt() }

    val nodes = Array(n) { BooleanArray(7) }
    val edges = Array(n) { mutableListOf<Int>() }

    val uf = UnionFind(n * 7)

    for (i in 0 until n) {
        val s = readInputLine()
        for ((j, c) in s.withIndex()) {
            if (c == '1') {
                nodes[i][j] = true
            }
        }
        for (j in 0 until 7) {
            if (nodes[i][j] && nodes[i][(j + 1) % 7]) {
                uf.unite(i * 7 + j, i * 7 + (j + 1) % 7)
            }
        }
    }

    repeat(m) {
        val (u, v) = readInputLine().split(" ").map { it.toInt() - 1 }
        edges[u].add(v)
        edges[v].add(u)

        for (i in 0 until 7) {
            if (nodes[u][i] && nodes[v][i]) {
                uf.unite(u * 7 + i, v * 7 + i)
            }
        }
    }

    repeat(q) {
        val (type, x, y) = readInputLine().split(" ").map { it.toInt() - 1 }

        when(type) {
            0 -> {
                nodes[x][y] = true
                for (e in edges[x]) {
                    if (nodes[x][y] && nodes[e][y]) {
                        uf.unite(x * 7 + y, e * 7 + y)
                    }
                }
                for (i in 0 until 7) {
                    if (nodes[x][i] && nodes[x][(i + 1) % 7]) {
                        uf.unite(x * 7 + i, x * 7 + (i + 1) % 7)
                    }
                }
            }
            else -> {
                builder.appendln(uf.sizeOf(x * 7))
            }
        }
    }

    print(builder.toString())
}

fun readInputLine(): String {
    return readLine()!!
}
0