oj.uz

Submission #240803

# Submission time Handle Problem Language Result Execution time Memory
240803 2020-06-21T08:16:46 Z wleung_bvg Synchronization (JOI13_synchronization) Kotlin
100 / 100
 2301 ms 111432 KB 
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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 12320 KB Output is correct
2 Correct 111 ms 12180 KB Output is correct
3 Correct 117 ms 12528 KB Output is correct
4 Correct 114 ms 12184 KB Output is correct
5 Correct 120 ms 12616 KB Output is correct
6 Correct 172 ms 14960 KB Output is correct
7 Correct 429 ms 29536 KB Output is correct
8 Correct 446 ms 30036 KB Output is correct
9 Correct 456 ms 29520 KB Output is correct
10 Correct 1234 ms 83076 KB Output is correct
11 Correct 1381 ms 83860 KB Output is correct
12 Correct 1248 ms 95692 KB Output is correct
13 Correct 1016 ms 75360 KB Output is correct
14 Correct 1447 ms 79520 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1311 ms 85384 KB Output is correct
2 Correct 1004 ms 85448 KB Output is correct
3 Correct 913 ms 89940 KB Output is correct
4 Correct 908 ms 92348 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 12532 KB Output is correct
2 Correct 114 ms 12688 KB Output is correct
3 Correct 121 ms 12660 KB Output is correct
4 Correct 127 ms 12556 KB Output is correct
5 Correct 121 ms 12512 KB Output is correct
6 Correct 189 ms 15572 KB Output is correct
7 Correct 465 ms 33728 KB Output is correct
8 Correct 1199 ms 95704 KB Output is correct
9 Correct 1437 ms 106184 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1429 ms 95876 KB Output is correct
2 Correct 1252 ms 102440 KB Output is correct
3 Correct 1342 ms 104788 KB Output is correct
4 Correct 1377 ms 102316 KB Output is correct

Subtask #5
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 12312 KB Output is correct
2 Correct 118 ms 12400 KB Output is correct
3 Correct 114 ms 12292 KB Output is correct
4 Correct 128 ms 12768 KB Output is correct
5 Correct 186 ms 15388 KB Output is correct
6 Correct 498 ms 31860 KB Output is correct
7 Correct 2301 ms 102868 KB Output is correct
8 Correct 1308 ms 107724 KB Output is correct
9 Correct 1261 ms 79516 KB Output is correct
10 Correct 1828 ms 86808 KB Output is correct
11 Correct 1528 ms 92156 KB Output is correct
12 Correct 1825 ms 94356 KB Output is correct
13 Correct 1740 ms 111432 KB Output is correct