結果

問題 No.1030 だんしんぐぱーりない
コンテスト
ユーザー yakamoto
提出日時 2020-04-26 01:01:37
言語 Kotlin
(2.1.0)
結果
AC  
実行時間 1,363 ms / 2,000 ms
コード長 6,466 bytes
コンパイル時間 22,619 ms
コンパイル使用メモリ 470,072 KB
実行使用メモリ 103,028 KB
最終ジャッジ日時 2024-11-08 09:32:17
合計ジャッジ時間 65,995 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.kt:56:11: warning: expected performance impact from inlining is insignificant. Inlining works best for functions with parameters of functional types
  private inline fun contains(a: Int, x: Int): Boolean = a < x
          ^

ソースコード

diff # 

import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.util.*
import kotlin.math.abs
import kotlin.math.max
import kotlin.math.min

fun packDGraph(n: Int, from: IntArray, to: IntArray): Array<IntArray> {
  val p = IntArray(n)
  val m = from.size
  for (i in 0 until m) {
    ++p[from[i]]
  }
  val g = Array(n){IntArray(p[it])}
  for (i in 0 until m) {
    g[from[i]][--p[from[i]]] = to[i]
  }
  return g
}
class SegmentTree(n: Int, val zero: Int, val f: (Int, Int) -> Int) {
  private val N =
    if (Integer.highestOneBit(n) == n) n
    else Integer.highestOneBit(n) shl 1

  private val dat = IntArray(2 * N){zero}

  fun update(i: Int, a: Int) {
    var ix = i + N
    dat[ix] = a
    while(ix > 1) {
      dat[ix shr 1] = f(dat[ix], dat[ix xor 1])
      ix = ix shr 1
    }
  }

  /**
   * [a, b)
   */
  fun query(a: Int, b: Int): Int {
    var res: Int = zero
    var left = a + N
    var right = b - 1 + N

    while(left <= right) {
      if ((left and 1) == 1) res = f(res, dat[left])
      if ((right and 1) == 0) res = f(res, dat[right])
      left = (left + 1) shr 1 // 右の子供なら右の親に移動
      right = (right - 1) shr 1 // 左の子供なら左の親に移動
    }

    return res
  }

  // 条件を満たすか。maxなら '>' minなら '<' が使える
  private inline fun contains(a: Int, x: Int): Boolean = a < x
  /**
   * @param x 左右どちらからか最初に a < x になる場所を探す
   * @param [a, b) 調べる範囲
   * @return -1
   */
  fun find(x: Int, a: Int = 0, b: Int = N, k: Int = 1, l: Int = 0, r: Int = N): Int {
    if (a >= r || l >= b) return -1// ノードが範囲からはずれてる
    if (!contains(dat[k], x)) return -1
    if (l + 1 == r) return l // 0-indexed

    val m = (l + r) / 2
    val lft = k * 2
    val rgt = lft + 1

    // 左から探す。右から探したい場合は左右を逆にすればいい
    val ans = find(x, a, b, lft, l, m)
    if (ans != -1) return ans
    return find(x, a, b, rgt, m, r)
  }
}
/**
 * (dist, parent, queue)
 */
fun traceBfs(g: Array<IntArray>, rt: Int = 0): Array<IntArray> {
  val n = g.size
  val q = IntArray(n)
  val d = IntArray(n)
  val p = IntArray(n){-2}
  var cur = 0
  var last = 1
  p[0] = -1
  q[0] = rt
  d[rt] = 0
  while (cur < last) {
    val v = q[cur++]
    for (u in g[v]) {
      if (p[u] == -2) {
        p[u] = v
        q[last++] = u
        d[u] = d[v] + 1
      }
    }
  }
  return arrayOf(d, p, q)
}

class LCA(N: Int, val dist: IntArray, par: IntArray, val K: Int) {
  private val anc = Array(K){IntArray(N)}
  init {
    for (u in 0 until N) {
      anc[0][u] = if (dist[u] == 0) u else par[u]
    }
    for (k in 1 until K) {
      for (u in 0 until N) {
        anc[k][u] = anc[k - 1][anc[k - 1][u]]
      }
    }
  }

  tailrec fun up(u: Int, d: Int, k: Int): Int {
    if (d == 0) return u
    else if (d % 2 == 1) return up(anc[k][u], d / 2, k + 1)
    else return up(u, d / 2, k + 1)
  }

  fun lca(uu: Int, vv: Int): Int {
    val d = min(dist[uu], dist[vv])
    var u = up(uu, dist[uu] - d , 0)
    var v = up(vv, dist[vv] - d, 0)
    if (u == v) return u
    for (k in K - 1 downTo 0) {
      if (anc[k][u] != anc[k][v]) {
        u = anc[k][u]
        v = anc[k][v]
      }
    }
    return anc[0][u]
  }
}

class Solver(stream: InputStream, private val out: java.io.PrintWriter) {
  fun solve() {
    val N = ni()
    val K = ni()
    val Q = ni()
    val C = na(N)
    val A = na(K, -1)
    val (from, to) = na2(N - 1, -1)
    val g = packDGraph(N, to, from)
    val ZERO = -2

    val mx = IntArray(N){C[it]}
    val (dist, par, que) = traceBfs(g)
    for (u in que) {
      for (v in g[u]) {
        mx[v] = max(mx[v], mx[u])
      }
    }
    debug(mx)
    val lca = LCA(N, dist, par, 20)

    if(isDebug) {
      for (i in 0 until N - 1) {
        for (j in i + 1 until N) {
          debug{"lca($i, $j)=${lca.lca(i ,j)}"}
        }
      }
    }

    val t = SegmentTree(K, ZERO){ a, b ->
      val res = if (a == ZERO) b
      else if (b == ZERO) a
      else lca.lca(a, b)
      debug{"f($a, $b)=$res"}
      res
    }

    for (i in 0 until K) {
      t.update(i, A[i])
    }

    for (i in 0 until Q) {
      if (ni() ==  1) {
        val x = ni() - 1
        val y = ni() - 1
        debug{"x:$x y:$y"}
        t.update(x, y)
      } else {
        val l = ni() - 1
        val r = ni()
        val anc = t.query(l, r)
        debug{"$l $r $anc"}
        out.println(mx[anc])
      }
    }
  }













































  private val isDebug = try {
    // なんか本番でエラーでる
    System.getenv("MY_DEBUG") != null
  } catch (t: Throwable) {
    false
  }

  private var tokenizer: StringTokenizer? = null
  private val reader = BufferedReader(InputStreamReader(stream), 32768)
  private fun next(): String {
    while (tokenizer == null || !tokenizer!!.hasMoreTokens()) {
      tokenizer = StringTokenizer(reader.readLine())
    }
    return tokenizer!!.nextToken()
  }

  private fun ni() = next().toInt()
  private fun nl() = next().toLong()
  private fun ns() = next()
  private fun na(n: Int, offset: Int = 0): IntArray {
    return map(n) { ni() + offset }
  }
  private fun nal(n: Int, offset: Int = 0): LongArray {
    val res = LongArray(n)
    for (i in 0 until n) {
      res[i] = nl() + offset
    }
    return res
  }

  private fun na2(n: Int, offset: Int = 0): Array<IntArray> {
    val a  = Array(2){IntArray(n)}
    for (i in 0 until n) {
      for (e in a) {
        e[i] = ni() + offset
      }
    }
    return a
  }

  private inline fun map(n: Int, f: (Int) -> Int): IntArray {
    val res = IntArray(n)
    for (i in 0 until n) {
      res[i] = f(i)
    }
    return res
  }

  private inline fun debug(msg: () -> String) {
    if (isDebug) System.err.println(msg())
  }

  private fun debug(a: LongArray) {
    debug { a.joinToString(" ") }
  }

  private fun debug(a: IntArray) {
    debug { a.joinToString(" ") }
  }

  private fun debug(a: BooleanArray) {
    debug { a.map { if (it) 1 else 0 }.joinToString("") }
  }

  private fun debugDim(A: Array<IntArray>) {
    if (isDebug) {
      for (a in A) {
        debug(a)
      }
    }
  }

  /**
   * 勝手にimport消されるのを防ぎたい
   */
  private fun hoge() {
    min(1, 2)
    max(1, 2)
    abs(-10)
  }
}

fun main() {
  val out = java.io.PrintWriter(System.out)
  Solver(System.`in`, out).solve()
  out.flush()
}
0