結果

問題 No.1266 7 Colors
ユーザー rutilicusrutilicus
提出日時 2020-10-25 12:45:40
言語 Kotlin
(1.9.23)
結果
AC  
実行時間 1,725 ms / 3,000 ms
コード長 2,865 bytes
コンパイル時間 21,949 ms
コンパイル使用メモリ 464,704 KB
実行使用メモリ 130,856 KB
最終ジャッジ日時 2024-07-21 20:50:39
合計ジャッジ時間 53,996 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 323 ms
51,732 KB
testcase_01 AC 320 ms
51,628 KB
testcase_02 AC 356 ms
51,592 KB
testcase_03 AC 1,589 ms
101,136 KB
testcase_04 AC 1,604 ms
112,724 KB
testcase_05 AC 1,473 ms
102,472 KB
testcase_06 AC 1,674 ms
118,588 KB
testcase_07 AC 1,697 ms
120,572 KB
testcase_08 AC 1,705 ms
121,492 KB
testcase_09 AC 1,361 ms
113,128 KB
testcase_10 AC 1,538 ms
108,224 KB
testcase_11 AC 1,647 ms
104,532 KB
testcase_12 AC 1,574 ms
106,032 KB
testcase_13 AC 1,637 ms
108,988 KB
testcase_14 AC 1,459 ms
102,140 KB
testcase_15 AC 1,517 ms
117,228 KB
testcase_16 AC 1,725 ms
105,636 KB
testcase_17 AC 1,561 ms
118,204 KB
testcase_18 AC 1,201 ms
120,020 KB
testcase_19 AC 1,259 ms
119,240 KB
testcase_20 AC 1,556 ms
130,856 KB
testcase_21 AC 1,012 ms
93,812 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