Submission #240803

#	Time	Username	Problem	Language	Result	Execution time	Memory
240803		wleung_bvg	Synchronization (JOI13_synchronization)	Kotlin (JVM)	100 / 100	2301 ms	111432 KiB

synchronization

import java.io.*
import java.math.*
import java.util.*

class Reader {
    private val In: BufferedReader
    private var st: StringTokenizer? = null
    constructor(inputStream: InputStream) {
        In = BufferedReader(InputStreamReader(inputStream))
    }
    fun next(): String {
        while (st == null || !st!!.hasMoreTokens()) st = StringTokenizer(In.readLine().trim())
        return st!!.nextToken()
    }
    fun nextInt(): Int = next().toInt()
    fun close(): Unit = In.close()
}

val In: Reader = Reader(System.`in`)
val Out: PrintWriter = PrintWriter(System.out)

fun main(args: Array<String>) {
    class Edge(var a: Int, var b: Int)
    val N = In.nextInt()
    val M = In.nextInt()
    val Q = In.nextInt()
    val L = IntArray(N + 1, {0})
    val R = IntArray(N + 1, {0})
    val P = IntArray(N + 1, {0})
    val active = BooleanArray(N - 1, {false})
    val adj = Array(N + 1, {ArrayList<Int>()})
    val E = Array(N - 1, {Edge(In.nextInt(), In.nextInt())})
    val cnt = IntArray(N + 1, {1})
    val last = IntArray(N + 1, {0})
    for (i in 0 until N - 1) {
        adj[E[i].a].add(i)
        adj[E[i].b].add(i)
    }
    fun dfs(v: Int, prev: Int) {
        for (i in adj[v]) {
            if (E[i].a == prev || E[i].b == prev) continue
            if (E[i].b == v) E[i].b = E[i].a.also { E[i].a = E[i].b }
            dfs(E[i].b, v)
        }
    }
    dfs(1, 0)
    fun isRoot(x: Int): Boolean {
        return P[x] == 0 || (x != L[P[x]] && x != R[P[x]])
    }
    fun connect(ch: Int, par: Int, hasCh: Boolean, isL: Boolean) {
        if (ch != 0) P[ch] = par
        if (hasCh) {
            if (isL) L[par] = ch
            else R[par] = ch
        }
    }
    fun rotate(x: Int) {
        val p = P[x]
        val g = P[p]
        val isRootP = isRoot(p)
        val isL = x == L[p]
        connect(if (isL) R[x] else L[x], p, true, isL)
        connect(p, x, true, !isL)
        connect(x, g, !isRootP, if (isRootP) false else p == L[g])
    }
    fun splay(x: Int) {
        while (!isRoot(x)) {
            val p = P[x]
            val g = P[p]
            if (!isRoot(p)) rotate(if ((x == L[p]) == (p == L[g])) p else x)
            rotate(x)
        }
    }
    fun expose(x: Int) {
        var last = 0
        var y = x
        while (y != 0) {
            splay(y)
            L[y] = last
            last = y
            y = P[y]
        }
        splay(x)
    }
    fun findRoot(x: Int): Int {
        var y = x
        expose(y)
        while (R[y] != 0) y = R[y]
        splay(y)
        return y
    }
    fun link(par: Int, ch: Int) {
        expose(ch)
        P[ch] = par
    }
    fun cutParent(ch: Int) {
        expose(ch)
        P[R[ch]] = 0
        R[ch] = 0
    }
    for (i in 0 until M) {
        val j = In.nextInt() - 1
        if (active[j]) {
            last[E[j].b] = cnt[findRoot(E[j].a)]
            cutParent(E[j].b)
            cnt[E[j].b] = last[E[j].b]
        } else {
            cnt[findRoot(E[j].a)] += cnt[E[j].b] - last[E[j].b]
            link(E[j].a, E[j].b)
        }
        active[j] = !active[j]
    }
    for (i in 0 until Q) Out.println(cnt[findRoot(In.nextInt())])
    In.close()
    Out.close()
}

Compilation message (stderr)

synchronization.kt:75:13: warning: name shadowed: last
        var last = 0
            ^

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 10 / 10
• Subtask 4: 20 / 20
• Subtask 5: 40 / 40