CODE FESTIVAL 2016 Final

Submission #6781696

Source codeソースコード

import java.io.PrintWriter
import java.util.*

fun main(args: Array<String>) = IO().exec {
    val n = int()
    val m = int()
    val utree = Utree(n + m)
    for (i in 0 until n) {
        val k = int()
        val l = IntArray(k){int()-1}
        for (j in 0 until k) utree.unite(i, n + l[j])
    }
    var isOk = true
    for (i in 0 until n) if (!utree.isSame(0, i)) isOk = false
    println(if (isOk) "YES" else "NO")
}

class Utree(val n: Int) {
    var par = Array(n){it}
    var rank = Array(n){0}
    var size = Array(n){1}

    fun find(x: Int): Int {
        return if (par[x] == x) {
            x
        } else {
            val ret = find(par[x])
            par[x] = ret
            ret
        }
    }

    fun unite(x_: Int, y_: Int) {
        val x = find(x_)
        val y = find(y_)
        if (x == y) return

        if (rank[x] < rank[y]) {
            par[x] = y
            size[y] += size[x]
        } else {
            par[y] = x
            size[x] += size[y]
            if (rank[x] == rank[y]) {
                rank[x] += 1
            }
        }
    }

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

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

class IO {
    val printable = 33..126
    val buffer = ByteArray(1024)
    var ptr = 0
    var buflen = 0
    val out = PrintWriter(System.out)
    fun hasNextByte(): Boolean = if (ptr < buflen) true else {
        ptr = 0
        buflen = System.`in`.read(buffer)
        buflen > 0
    }
    fun readByte(): Byte = if (hasNextByte()) buffer[ptr++] else -1
    fun hasNext(): Boolean {
        while (hasNextByte() && buffer[ptr] !in printable) ptr++
        return hasNextByte()
    }
    fun string(): String {
        if (!hasNext()) throw NoSuchElementException()
        val sb = StringBuilder()
        var b = readByte()
        while (b in printable) {
            sb.appendCodePoint(b.toInt())
            b = readByte()
        }
        return sb.toString()
    }
    fun long(): Long {
        if (!hasNext()) throw NoSuchElementException()
        var n = 0L
        var minus = false
        var b = readByte()
        if (b == '-'.toByte()) {
            minus = true
            b = readByte()
        }
        if (b !in '0'.toByte()..'9'.toByte()) {
            throw NumberFormatException()
        }
        while (true) {
            if (b in '0'.toByte()..'9'.toByte()) {
                n *= 10
                n += b - '0'.toByte()
            } else if (b == (-1).toByte() || b !in printable) {
                return if (minus) -n else n
            } else {
                throw NumberFormatException()
            }
            b = readByte()
        }
    }
    fun int(): Int {
        val nl = long()
        if (nl !in Integer.MIN_VALUE..Integer.MAX_VALUE) throw NumberFormatException()
        return nl.toInt()
    }
    fun double(): Double = string().toDouble()
    fun print(obj: Any) = out.print(obj)
    fun print(i: Int) = out.print(i)
    fun print(l: Long) = out.print(l)
    fun println(obj: Any) = out.println(obj)
    fun println(i: Int) = out.println(i)
    fun println(l: Long) = out.println(l)
    inline fun exec(block: IO.() -> Unit) {
        block()
        out.flush()
    }
}

Submission

Task問題 C - Interpretation
User nameユーザ名 へのく
Created time投稿日時
Language言語 Kotlin (1.0.0)
Status状態 AC
Score得点 400
Source lengthソースコード長 3397 Byte
File nameファイル名
Exec time実行時間 397 ms
Memory usageメモリ使用量 51648 KB

Test case

Set

Set name Score得点 / Max score Cases
sample - sample-01.txt,sample-02.txt
dataset1 200 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt
dataset2 200 / 200 sample-01.txt,sample-02.txt,01-01.txt,01-02.txt,01-03.txt,01-04.txt,01-05.txt,01-06.txt,01-07.txt,01-08.txt,01-09.txt,01-10.txt,02-01.txt,02-02.txt,02-03.txt,02-04.txt,02-05.txt,02-06.txt,02-07.txt,02-08.txt,02-09.txt,02-10.txt,02-11.txt,02-12.txt,02-13.txt,sample-01.txt,sample-02.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
01-01.txt AC 161 ms 27292 KB
01-02.txt AC 170 ms 27308 KB
01-03.txt AC 176 ms 29468 KB
01-04.txt AC 176 ms 29212 KB
01-05.txt AC 175 ms 29348 KB
01-06.txt AC 173 ms 29468 KB
01-07.txt AC 173 ms 29344 KB
01-08.txt AC 174 ms 31388 KB
01-09.txt AC 174 ms 29480 KB
01-10.txt AC 179 ms 27432 KB
02-01.txt AC 311 ms 39544 KB
02-02.txt AC 397 ms 48700 KB
02-03.txt AC 310 ms 36412 KB
02-04.txt AC 379 ms 51648 KB
02-05.txt AC 382 ms 47108 KB
02-06.txt AC 371 ms 50568 KB
02-07.txt AC 378 ms 47272 KB
02-08.txt AC 365 ms 44348 KB
02-09.txt AC 358 ms 45132 KB
02-10.txt AC 354 ms 42488 KB
02-11.txt AC 352 ms 41212 KB
02-12.txt AC 359 ms 41964 KB
02-13.txt AC 316 ms 41896 KB
sample-01.txt AC 162 ms 27288 KB
sample-02.txt AC 161 ms 27292 KB