Submission #6781696


Source Code Expand

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 Info

Submission Time
Task C - Interpretation
User henoc
Language Kotlin (1.0.0)
Score 400
Code Size 3397 Byte
Status AC
Exec Time 397 ms
Memory 51648 KB

Judge Result

Set Name sample dataset1 dataset2
Score / Max Score 0 / 0 200 / 200 200 / 200
Status
AC × 2
AC × 12
AC × 27
Set Name Test Cases
sample sample-01.txt, sample-02.txt
dataset1 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 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
Case Name Status Exec Time Memory
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