結果

問題 No.1266 7 Colors
ユーザー rutilicusrutilicus
提出日時 2020-10-25 12:45:40
言語 Kotlin
(2.1.0)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 19
権限があれば一括ダウンロードができます
コンパイルメッセージ
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