結果
| 問題 |
No.1364 [Renaming] Road to Cherry from Zelkova
|
| コンテスト | |
| ユーザー |
 da_louis
|
| 提出日時 | 2021-01-26 00:40:30 |
| 言語 | Kotlin (2.1.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 21,300 bytes |
| コンパイル時間 | 26,384 ms |
| コンパイル使用メモリ | 500,712 KB |
| 実行使用メモリ | 132,788 KB |
| 最終ジャッジ日時 | 2024-06-23 00:32:08 |
| 合計ジャッジ時間 | 57,207 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 20 WA * 25 |
コンパイルメッセージ
Main.kt:266:13: warning: 'appendln(Int): kotlin.text.StringBuilder /* = java.lang.StringBuilder */' is deprecated. Use appendLine instead. Note that the new method always appends the line feed character '\n' regardless of the system line separator.
appendln(n)
^
Main.kt:299:48: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
^
Main.kt:299:62: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
^
Main.kt:300:68: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
^
Main.kt:332:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '-'.toByte()) {
^
Main.kt:358:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '-'.toByte()) {
^
Main.kt:364:22: warning: 'toByte(): Byte' is deprecated. Conversion of Char to Number is deprecated. Use Char.code property instead.
if (b == '.'.toByte()) {
^
ソースコード
import java.io.ByteArrayInputStream
import java.io.ByteArrayOutputStream
import java.io.PrintStream
import java.util.*
import kotlin.collections.ArrayDeque
fun main() = if (localEnv && execChecker) checker() else contest296g()
fun contest296g() = solve()
@OptIn(ExperimentalStdlibApi::class)
private fun solve() = Messiah_contest296g(MOD).exec {
data class Edge(val from: Int, val to: Int, val length: Long, val amount: Long)
val (n, m) = readInt() to readInt()
val edges = Array(m) { Edge(readInt(), readInt(), readLong(), readLong()) }
val revGraph = Array(n + 1) { mutableListOf<Int>() }
edges.forEach { (u, v) -> revGraph[v].add(u) }
// 閉路検出
val visitedNodes = mutableSetOf<Int>()
val queue = ArrayDeque(listOf(n))
while (queue.isNotEmpty()) {
val curr = queue.removeFirst()
if (!visitedNodes.add(curr)) continue
for (before in revGraph[curr]) queue.addLast(before)
}
val scc = SCC(n + 1).apply {
edges.forEach { (u, v) -> if (u in visitedNodes && v in visitedNodes) addEdge(u, v) }
}.build()
// 0-N 間で閉路があった場合 INF 、 たどり着けない場合は 0
when {
0 !in visitedNodes -> "0"
scc.size != n + 1 -> "INF"
else -> null
}?.let { return@exec println(it) }
val dp = Array(n + 1) { Mint.ZERO }
val graph = Array(n + 1) { mutableListOf<Edge>() }
// 0-N 間の辺だけ使う
edges.forEach { if (it.from in visitedNodes && it.to in visitedNodes) graph[it.from].add(it) }
val visitCount = Array(n + 1) { Mint.ZERO }.apply { this[0] = Mint.ONE }
for ((curr) in scc) for ((_, next, length, amount) in graph[curr]) {
dp[next] += dp[curr] + length.toMint() * amount * visitCount[curr]
visitCount[next] += visitCount[curr] * amount
}
val answer = dp.last()
println(answer)
}
/**
* convert from [AtCoderLibraryForJava - SCC](https://github.com/NASU41/AtCoderLibraryForJava/blob/ee794a298f6d16ab24bd9316e7cae8a9155510e5/SCC/SCC.java)
*/
private class SCC(private val n: Int) {
private class Edge(var from: Int, var to: Int)
private var m = 0
private val unorderedEdges: ArrayList<Edge> = ArrayList()
private val start: IntArray = IntArray(n + 1)
private val ids: IntArray = IntArray(n)
private var hasBuilt = false
fun addEdge(from: Int, to: Int) {
rangeCheck(from)
rangeCheck(to)
unorderedEdges.add(Edge(from, to))
start[from + 1]++
m++
}
fun id(i: Int): Int {
if (!hasBuilt) {
throw UnsupportedOperationException(
"Graph hasn't been built."
)
}
rangeCheck(i)
return ids[i]
}
fun build(): Array<IntArray> {
for (i in 1..n) {
start[i] += start[i - 1]
}
val orderedEdges = arrayOfNulls<Edge>(m)
val count = IntArray(n + 1)
System.arraycopy(start, 0, count, 0, n + 1)
for (e in unorderedEdges) {
orderedEdges[count[e.from]++] = e
}
var nowOrd = 0
var groupNum = 0
var k = 0
// parent
val par = IntArray(n)
val vis = IntArray(n)
val low = IntArray(n)
val ord = IntArray(n)
java.util.Arrays.fill(ord, -1)
// u = lower32(stack[i]) : visiting vertex
// j = upper32(stack[i]) : jth child
val stack = LongArray(n)
// size of stack
var ptr = 0
// non-recursional DFS
for (i in 0 until n) {
if (ord[i] >= 0) continue
par[i] = -1
// vertex i, 0th child.
stack[ptr++] = 0L shl 32 or i.toLong()
// stack is not empty
while (ptr > 0) {
// last element
val p = stack[--ptr]
// vertex
val u = (p and 0xffffffffL).toInt()
// jth child
var j = (p ushr 32).toInt()
if (j == 0) { // first visit
ord[u] = nowOrd++
low[u] = ord[u]
vis[k++] = u
}
if (start[u] + j < count[u]) { // there are more children
// jth child
val to = orderedEdges[start[u] + j]!!.to
// incr children counter
stack[ptr++] += 1L shl 32
if (ord[to] == -1) { // new vertex
stack[ptr++] = 0L shl 32 or to.toLong()
par[to] = u
} else { // backward edge
low[u] = kotlin.math.min(low[u], ord[to])
}
} else { // no more children (leaving)
while (j-- > 0) {
val to = orderedEdges[start[u] + j]!!.to
// update lowlink
if (par[to] == u) low[u] = kotlin.math.min(low[u], low[to])
}
if (low[u] == ord[u]) { // root of a component
while (true) { // gathering verticies
val v = vis[--k]
ord[v] = n
ids[v] = groupNum
if (v == u) break
}
groupNum++ // incr the number of components
}
}
}
}
for (i in 0 until n) {
ids[i] = groupNum - 1 - ids[i]
}
val counts = IntArray(groupNum)
for (x in ids) counts[x]++
val groups = Array(groupNum) { intArrayOf() }
for (i in 0 until groupNum) {
groups[i] = IntArray(counts[i])
}
for (i in 0 until n) {
val cmp = ids[i]
groups[cmp][--counts[cmp]] = i
}
hasBuilt = true
return groups
}
private fun rangeCheck(i: Int) {
if (i < 0 || i >= n) {
throw IndexOutOfBoundsException(String.format("Index %d out of bounds for length %d", i, n))
}
}
}
private fun Long.toMint() = Mint(this)
private fun Int.toMint() = Mint(this.toLong())
@Suppress("unused")
private class Mint(value: Long) {
constructor(other: Mint) : this(other.value)
private val value = (value % MOD).let { if (it < 0) it + MOD else it }
operator fun unaryPlus() = this
operator fun unaryMinus() = Mint(MOD - this.value)
operator fun inc() = this.plus(1)
operator fun dec() = this.minus(1)
operator fun plus(other: Long) = Mint(this.value + other)
operator fun plus(other: Mint) = this.plus(other.value)
operator fun minus(other: Long) = Mint(this.value - other)
operator fun minus(other: Mint) = this.plus(-other)
operator fun times(other: Long) = Mint(this.value * Mint(other).value)
operator fun times(other: Mint) = this.times(other.value)
operator fun div(other: Long) = this.times(other.inv())
operator fun div(other: Mint) = this.div(other.value)
fun inv() = Mint(modPow(this.toLong(), MOD - 2L))
fun mod(mod: Long) = Mint(this.value % mod)
fun pow(other: Long) = Mint(modPow(this.value, other))
fun toLong() = this.value
override fun toString() = this.value.toString()
override fun hashCode() = value.hashCode()
override fun equals(other: Any?): Boolean {
if (this === other) return true
if (javaClass != other?.javaClass) return false
other as Mint
return value == other.value
}
companion object {
val ZERO = Mint(0)
val ONE = Mint(1)
val TWO = Mint(2)
val TEN = Mint(10)
private fun modPow(n: Long, p: Long): Long {
var x = n % MOD
var y = p
var result = 1L
while (y > 0) {
if (y % 2 == 1L) result = (result * x) % MOD
y = y shr 1
x = (x * x) % MOD
}
return result
}
}
}
private const val MOD = 1_000_000_007
// region kokokara template dayo (^o^)
private const val execChecker = false
private val localEnv =
runCatching { "ENABLE_DEBUG_MODE_FOR_COMPETITIVE_PROGRAMING" in System.getenv() }.getOrNull() ?: false
private fun checker() = Messiah_contest296g(MOD).exec {
debugln("#######################################################")
debugln("############### executing check mode. ###############")
debugln("#######################################################")
fun getOutPut(input: String, action: () -> Unit): String {
System.setIn(ByteArrayInputStream(input.toByteArray()))
val sysOut = ByteArrayOutputStream()
System.setOut(PrintStream(sysOut))
action()
return sysOut.toString()
}
val wrongCases = mutableSetOf<List<String>>()
while (wrongCases.size < 10) {
/*
examples
val randomString = (1..20).map { ('a'..'z').random() }.joinToString("")
val randomNum = Random.nextInt(0,2000)
*/
val n = 0
val input = buildString {
appendln(n)
}
val solve = getOutPut(input, ::solve)
val greedy = getOutPut(input, ::greedy)
if (solve != greedy && wrongCases.add(listOf(solve, greedy))) {
debugln("#################### wrong case: ${wrongCases.size} ####################")
debugln("input:")
debugln(input)
debugln("solve:")
debugln(solve)
debugln("greedy:")
debugln(greedy)
}
}
}
private fun greedy() = Messiah_contest296g(MOD).exec {
TODO()
}
@Suppress("ClassName", "unused", "FunctionName", "PropertyName")
private class Messiah_contest296g(private val mod: Int) {
//////////////////////////////////////////////////
// IO
//////////////////////////////////////////////////
private val input = System.`in`
private val buffer = ByteArray(1024)
private var pointer = 0
private var bufferLength = 0
private val sb = StringBuilder()
private fun Byte.isPrintable() = this in 33..126
private fun Byte.isNumeric() = this in '0'.toByte()..'9'.toByte()
private fun Byte.toNumVal() = if (this.isNumeric()) this - '0'.toByte() else error("$this is not numeric")
private val lineSeparator: String = System.lineSeparator()
private fun hasNextByte(): Boolean {
return if (pointer < bufferLength) true else {
pointer = 0
bufferLength = input.read(buffer)
bufferLength > 0
}
}
private fun readByte(): Byte = if (hasNextByte()) buffer[pointer++] else -1
private fun skipUnprintable() = run { while (hasNextByte() && !buffer[pointer].isPrintable()) pointer++ }
private fun hasNext(): Boolean = run { skipUnprintable() }.run { hasNextByte() }
private fun hasNextOrError() = if (!hasNext()) error("has no next element.") else Unit
fun readString(): String {
hasNextOrError()
val sb = StringBuilder()
var b = readByte()
while (b.isPrintable()) {
sb.appendCodePoint(b.toInt())
b = readByte()
}
return sb.toString()
}
fun readLong(): Long {
hasNextOrError()
var n = 0L
var negative = false
var b = readByte()
if (b == '-'.toByte()) {
negative = true
b = readByte()
}
if (!b.isNumeric()) error("$b is not numeric.")
while (true) {
when {
b.isNumeric() -> n = n * 10 + b.toNumVal()
b.toInt() == -1 || !b.isPrintable() -> return if (negative) -n else n
else -> error("failed to parse. [n=$n, b=$b]")
}
b = readByte()
}
}
fun readInt() = readLong()
.let { if (it in Int.MIN_VALUE..Int.MAX_VALUE) it.toInt() else error("$it is not in range of Int.") }
fun readIntAsIndex() = readInt().dec()
fun readDouble(): Double {
hasNextOrError()
var n = 0.0
var div = 1.0
var negative = false
var b = readByte()
if (b == '-'.toByte()) {
negative = true
b = readByte()
}
do n = n * 10 + b.toNumVal()
while (run { b = readByte() }.run { b.isNumeric() })
if (b == '.'.toByte()) {
while (run { b = readByte() }.run { b.isNumeric() })
n += b.toNumVal() / (run { div *= 10 }.run { div })
}
return if (negative) -n else n
}
fun readString(size: Int): Array<String> = Array(size) { readString() }
@Suppress("UNUSED_PARAMETER")
fun readChars(h: Int, w: Int): Array<CharArray> = Array(h) { readString().toCharArray() }
fun readLong(size: Int): LongArray = LongArray(size) { readLong() }
fun readLong(h: Int, w: Int): Array<LongArray> = Array(h) { readLong(w) }
fun readInt(size: Int): IntArray = IntArray(size) { readInt() }
fun readInt(h: Int, w: Int): Array<IntArray> = Array(h) { readInt(w) }
fun readIntAsIndex(size: Int): IntArray = IntArray(size) { readIntAsIndex() }
fun readIntAsIndex(h: Int, w: Int): Array<IntArray> = Array(h) { readIntAsIndex(w) }
fun readDouble(size: Int): DoubleArray = DoubleArray(size) { readDouble() }
fun readDouble(h: Int, w: Int): Array<DoubleArray> = Array(h) { readDouble(w) }
fun readBooleanWithSeparator(size: Int, trueElement: String): BooleanArray =
BooleanArray(size) { readString() == trueElement }
fun readBooleanWithSeparator(h: Int, w: Int, trueElement: String): Array<BooleanArray> =
Array(h) { readBooleanWithSeparator(w, trueElement) }
@Suppress("UNUSED_PARAMETER")
fun readBooleanWithoutSeparator(size: Int, trueElement: Char): BooleanArray =
readString().map { it == trueElement }.toBooleanArray()
fun readBooleanWithoutSeparator(h: Int, w: Int, trueElement: Char): Array<BooleanArray> =
Array(h) { readBooleanWithoutSeparator(w, trueElement) }
fun println(): Unit = run { sb.append(lineSeparator) }
fun print(any: Any): Unit = run { sb.append(any.toString()) }
fun println(any: Any): Unit = run { sb.append(any.toString() + lineSeparator) }
fun flush() = run { kotlin.io.println(sb); sb.clear() }
fun debugln(any: Any): Unit = run { if (localEnv) System.err.println(any) }
fun debugln(): Unit = run { if (localEnv) System.err.println() }
fun debugln(action: () -> Unit): Unit = run { if (localEnv) action() }
fun exec(action: Messiah_contest296g.() -> Unit) {
var t: Throwable? = null
Thread(null, { action() }, "solve", 128 * 1024 * 1024)
.apply { setUncaughtExceptionHandler { _, t1 -> t = t1 } }
.apply { start() }.join()
t?.let { throw it }
kotlin.io.print(sb)
}
fun readLine(): Nothing = error("readLine is disabled.")
//////////////////////////////////////////////////
// MOD
//////////////////////////////////////////////////
fun Long.invertMod(): Long = invGcd(this).second
fun Long.safeMod(): Long = (this % MOD).let { if (it < 0) it + MOD else it }
fun Long.modPow(p: Long): Long {
var x = this % MOD
var y = p
var result = 1L
while (y > 0) {
if (y % 2 == 1L) result = (result * x) % MOD
y = y shr 1
x = (x * x) % MOD
}
return result
}
fun Long.modPow(p: Long, m: Int): Long {
var x = this % m
var y = p
var result = 1L
while (y > 0) {
if (y % 2 == 1L) result = (result * x) % m
y = y shr 1
x = (x * x) % m
}
return result
}
fun invGcd(a: Long): Pair<Long, Long> {
val am = a.safeMod()
if (a == 0L) return MOD.toLong() to 0L
var s = MOD.toLong()
var t = am
var m0 = 0L
var m1 = 1L
while (t != 0L) {
val u = s / t
s -= t * u
m0 -= m1 * u
var temp = s
s = t
t = temp
temp = m0
m0 = m1
m1 = temp
}
if (m0 < 0) m0 += MOD / s
return s to m0
}
//////////////////////////////////////////////////
// Misc
//////////////////////////////////////////////////
/**
* `n.indices()` is sugar syntax of `0 until n`.
*/
val Int.indices: IntRange get() = 0 until this
/**
* `[index] in [this]` is sugar syntax of `index in 0 until [this]`.
*/
operator fun Int.contains(index: Int): Boolean = index in this.indices
/**
* `[this].mapIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
*/
inline fun <R> Int.mapIndices(transform: (Int) -> R): List<R> = this.indices.map(transform)
/**
* `[this].mapIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun <R> Int.mapIndices(x: Int, transform: (Int, Int) -> R): List<List<R>> =
this.mapIndices { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
/**
* `[this].mapIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun <R> Int.flatMapIndices(x: Int, transform: (Int, Int) -> R): List<R> =
this.indices.flatMap { y1 -> x.mapIndices { x1 -> transform(y1, x1) } }
/**
* `[this].forEachIndices { transform }` is sugar syntax of `(0 until [this]).map{ transform(it) }`.
*/
inline fun Int.forEachIndices(transform: (Int) -> Unit): Unit = this.indices.forEach(transform)
/**
* `[this].forEachIndices(x) { transform }` is sugar syntax of
* `(0 until [this]).map{ y1-> (0 until [x]).map { x1-> transform(y1,x1) } }`.
*/
inline fun Int.forEachIndices(x: Int, transform: (Int, Int) -> Unit): Unit =
this.forEachIndices { y1 -> x.forEachIndices { x1 -> transform(y1, x1) } }
/**
* get characters numeric value.
* e.g.: '0' to 0
*/
fun Char.toNumericValue(): Int = this - '0'
fun Char.caseToIndexedValue(): Int = this - 'a'
// fun Char.isLowerCase() = this in 'a'..'z'
//
// fun Char.isUpperCase() = this in 'A'..'Z'
/**
* make triple. e.g.:`1 to 2 to 3`
*/
infix fun <A, B, C> Pair<A, B>.to(c: C): Triple<A, B, C> = Triple(this.first, this.second, c)
fun YesNo(b: Boolean): String = if (b) Yes else No
val Yes = "Yes"
val No = "No"
fun YES_NO(b: Boolean): String = if (b) YES else NO
val YES = "YES"
val NO = "NO"
fun IntArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun LongArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun CharArray.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun <T> Array<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun <T> MutableList<T>.swap(a: Int, b: Int): Unit = run { val temp = this[a]; this[a] = this[b]; this[b] = temp }
fun IntArray.changeMinOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.min(this[i], v) }
fun IntArray.changeMaxOf(i: Int, v: Int): Unit = run { this[i] = kotlin.math.max(this[i], v) }
fun LongArray.changeMinOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.min(this[i], v) }
fun LongArray.changeMaxOf(i: Int, v: Long): Unit = run { this[i] = kotlin.math.max(this[i], v) }
/**
* same usage as `IntArray.scan`, but it will faster than that.
*/
inline fun IntArray.scanArray(initial: Int, operation: (acc: Int, Int) -> Int): IntArray {
val accumulator = IntArray(this.size + 1).apply { this[0] = initial }
for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
return accumulator
}
/**
* same usage as `LongArray.scan`, but it will faster than that.
*/
inline fun LongArray.scanArray(initial: Long, operation: (acc: Long, Long) -> Long): LongArray {
val accumulator = LongArray(this.size + 1).apply { this[0] = initial }
for (i in this.indices) accumulator[i + 1] = operation(accumulator[i], this[i])
return accumulator
}
/**
* same usage as `IntArray.scanReduce`, but it will faster than that.
*/
inline fun IntArray.scanReduceArray(operation: (acc: Int, Int) -> Int): IntArray {
val accumulator = IntArray(this.size).apply { this[0] = this@scanReduceArray[0] }
for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
return accumulator
}
/**
* same usage as `LongArray.scanReduce`, but it will faster than that.
*/
inline fun LongArray.scanReduceArray(operation: (acc: Long, Long) -> Long): LongArray {
val accumulator = LongArray(this.size).apply { this[0] = this@scanReduceArray[0] }
for (i in 1..this.lastIndex) accumulator[i] = operation(accumulator[i - 1], this[i])
return accumulator
}
}
// endregion kokomade template dayo (^o^)