結果
問題 | No.1442 I-wate Shortest Path Problem |
ユーザー | iaNTU |
提出日時 | 2021-03-11 01:12:36 |
言語 | Kotlin (1.9.23) |
結果 |
AC
|
実行時間 | 1,715 ms / 3,000 ms |
コード長 | 4,958 bytes |
コンパイル時間 | 17,830 ms |
コンパイル使用メモリ | 458,284 KB |
実行使用メモリ | 117,684 KB |
最終ジャッジ日時 | 2024-04-20 18:43:55 |
合計ジャッジ時間 | 43,156 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 267 ms
50,200 KB |
testcase_01 | AC | 260 ms
49,796 KB |
testcase_02 | AC | 400 ms
55,256 KB |
testcase_03 | AC | 539 ms
63,556 KB |
testcase_04 | AC | 391 ms
54,332 KB |
testcase_05 | AC | 353 ms
52,856 KB |
testcase_06 | AC | 510 ms
63,584 KB |
testcase_07 | AC | 373 ms
54,644 KB |
testcase_08 | AC | 543 ms
62,844 KB |
testcase_09 | AC | 420 ms
57,060 KB |
testcase_10 | AC | 559 ms
64,776 KB |
testcase_11 | AC | 537 ms
63,764 KB |
testcase_12 | AC | 1,348 ms
117,684 KB |
testcase_13 | AC | 767 ms
104,620 KB |
testcase_14 | AC | 1,178 ms
105,752 KB |
testcase_15 | AC | 1,138 ms
106,368 KB |
testcase_16 | AC | 1,333 ms
107,576 KB |
testcase_17 | AC | 1,576 ms
109,252 KB |
testcase_18 | AC | 1,508 ms
109,812 KB |
testcase_19 | AC | 1,421 ms
114,348 KB |
testcase_20 | AC | 1,715 ms
109,576 KB |
testcase_21 | AC | 1,583 ms
110,396 KB |
testcase_22 | AC | 699 ms
104,120 KB |
testcase_23 | AC | 1,334 ms
117,512 KB |
testcase_24 | AC | 690 ms
104,080 KB |
testcase_25 | AC | 1,514 ms
114,260 KB |
testcase_26 | AC | 983 ms
102,972 KB |
コンパイルメッセージ
Main.kt:78:13: warning: name shadowed: a var a = x ^ Main.kt:79:13: warning: name shadowed: b var b = y ^ Main.kt:135:10: warning: name shadowed: x for (x in ans) println(x) ^ Main.kt:146:26: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. private val lb = '0'.toByte() ^ Main.kt:147:26: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. private val rb = '9'.toByte() ^ Main.kt:187:26: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead. n += b - '0'.toByte() ^
ソースコード
import java.io.PrintWriter import java.util.* fun PrintWriter.solve() { val scan=FastScanner() val n = scan.nextInt() val k = scan.nextInt() //Making Graph-begin val cnt = IntArray(n + k) val a = IntArray(n - 1) val b = IntArray(n - 1) val c = IntArray(n - 1) for (i in 0 until n - 1) { a[i] = scan.nextInt() - 1 b[i] = scan.nextInt() - 1 c[i] = scan.nextInt() ++cnt[a[i]] ++cnt[b[i]] } val m = IntArray(k) val p = IntArray(k) val x = Array(k) {IntArray(0)} for (i in 0 until k) { m[i] = scan.nextInt() p[i] = scan.nextInt() cnt[n + i] += m[i] x[i] = IntArray(m[i]) { scan.nextInt() - 1 } for (j in x[i]) ++cnt[j] } val g = Array(n + k) { Array(0) { Pair<Int, Int>(0, 0) } } for (i in 0 until n + k) g[i] = Array(cnt[i]) { Pair<Int, Int>(0, 0) } for (i in 0 until n - 1) { g[a[i]][--cnt[a[i]]] = Pair<Int, Int>(b[i], c[i]) g[b[i]][--cnt[b[i]]] = Pair<Int, Int>(a[i], c[i]) } for (i in 0 until k) { for (j in x[i]) { g[n + i][--cnt[n + i]] = Pair<Int, Int>(j, 0) g[j][--cnt[j]] = Pair<Int, Int>(n + i, p[i]) } } //Making Graph-end //LCA-begin val logn = 16 val dep = IntArray(n) { -1 } val dis = LongArray(n) { 0 } val nxt = Array(logn + 1) { Array(n) { -1 } } val que = IntArray(n) var qf = 0 var qb = 0 dep[0] = 0 que[qb++]=0 while (qb > qf) { val cur = que[qf++] for ((to, cost) in g[cur]) { if (to < n && dep[to] == -1) { dep[to] = dep[cur] + 1 dis[to] = dis[cur] + cost nxt[0][to] = cur que[qb++] = to } } } nxt[0][0] = 0 for (j in 0 until logn) { for (i in 0 until n) { nxt[j + 1][i] = nxt[j][nxt[j][i]] } } fun lca(x: Int, y: Int): Int { var a = x var b = y if (dep[a] > dep[b]) { a = y b = x } val d = dep[b] - dep[a] for (j in logn downTo 0) { if (d and (1 shl j) > 0) b = nxt[j][b] } if (a == b) return a for (j in logn downTo 0) { if (nxt[j][a] != nxt[j][b]) { a = nxt[j][a] b = nxt[j][b] } } return nxt[0][a] } //LCA-end val q = scan.nextInt() val ans = LongArray(q) { 0L } val u = IntArray(q) { 0 } val v = IntArray(q) { 0 } for (i in 0 until q) { u[i] = scan.nextInt() - 1 v[i] = scan.nextInt() - 1 ans[i] = dis[u[i]] + dis[v[i]] - 2 * dis[lca(u[i], v[i])] } //Dijkstra-begin val pq = PriorityQueue<Long>() for (i in 0 until k) { val dp = LongArray(n + k) { 1000000000000000000L } dp[n + i] = 0 pq.add((n + i).toLong()) while (pq.isNotEmpty()) { var d = pq.remove() val cur = (d % (n + k)).toInt() d /= n + k if (dp[cur] < d) continue for ((to, cost) in g[cur]) { if (dp[to] > d + cost) { dp[to] = d + cost pq.add((d + cost) * (n + k) + to) } } } for (j in 0 until q) { if (ans[j] > dp[u[j]] + dp[v[j]] + p[i]) { ans[j] = dp[u[j]] + dp[v[j]] + p[i] } } } //Dijkstra-end for (x in ans) println(x) } fun main() { val writer = PrintWriter(System.out, false) writer.solve() writer.flush() } private class FastScanner { private val printable = 33..126 private val lb = '0'.toByte() private val rb = '9'.toByte() val `in` = System.`in` val buffer = ByteArray(65536) var ptr = 0 var buflen = 0 fun hasNextByte(): Boolean { if (ptr < buflen) { return true } else { ptr = 0 buflen = `in`.read(buffer) if (buflen <= 0) { return false } } return true } fun readByte(): Byte { return if (hasNextByte()) buffer[ptr++] else return -1 } fun hasNext(): Boolean { while (hasNextByte() && buffer[ptr] !in printable) ptr++ return hasNextByte() } fun next(): String { val sb = StringBuilder() var b = readByte() while (b in printable) { sb.appendCodePoint(b.toInt()) b = readByte() } return sb.toString() } fun nextInt(): Int { var n = 0 var b = readByte() while (b < lb || b > rb) b = readByte() while (lb <= b && b <= rb) { n *= 10 n += b - '0'.toByte() b = readByte() } return n } fun nextDouble(): Double { return next().toDouble() } }