Submission #39658176

---

Source Code Expand

fun main() {
    val (n, m) = readLine()!!.split(" ").map { it.toInt() }

    val diff = n
    val uf = UnionFind(n + diff + 1)

    for(i in 1..n) {
        uf.union(i, i + diff)
    }

    var x = 0
    repeat(m) {
        val (a, b, c, d) = readLine()!!.split(" ")

        val aa =if(b == "R") {
            a.toInt()
        } else {
            a.toInt() + diff
        }

        val cc = if(d == "R") {
            c.toInt()
        } else {
            c.toInt() + diff
        }

        if(uf.isSame(aa, cc)) {
            x++
        }

        uf.union(aa, cc)
    }
    val num = (1..n + diff).map { uf.find(it) }.distinct().size

    println("$x ${num - x}")
}

private class UnionFind(n: Int){
    private val roots = IntArray(n){ it }
    private val ranks = IntArray(n){ 1 }

    fun find(i: Int): Int{
        if(roots[i] != i){
            roots[i] = find(roots[i])
        }

        return roots[i]
    }

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

    fun union(x: Int, y: Int){
        val rootX = find(x)
        val rootY = find(y)

        if(rootX == rootY) {
            return
        }
        if(ranks[rootX] > ranks[rootY]){
            roots[rootY] = rootX
            ++ranks[rootX]
        }else{
            roots[rootX] = rootY
            ++ranks[rootY]
        }
    }
}

Submission Info

Compile Error

warning: ATTENTION!
This build uses unsafe internal compiler arguments:

-XXLanguage:+InlineClasses

This mode is not recommended for production use,
as no stability/compatibility guarantees are given on
compiler or generated code. Use it at your own risk!

Judge Result