Submission #2120296


Source Code Expand

import java.util.*
import java.io.IOException

val DEBUG = false

val P = 1000000007L

//data class FiniteField(val x: Long) {
//  val p = 1000000007L
//  operator fun plus(o: FiniteField) = FiniteField((x + o.x) % p)
//  operator fun minus(o: FiniteField) = FiniteField((x + p - o.x) % p)
//  operator fun times(o: FiniteField) = FiniteField((x * o.x) % p)
//}



internal class FastScanner {
  private val `in` = System.`in`
  private val buffer = ByteArray(1024 * 1024)
  private var ptr = 0
  private var buflen = 0
  private fun hasNextByte(): Boolean {
    if (ptr < buflen) {
      return true
    } else {
      ptr = 0
      try {
        buflen = `in`.read(buffer)
      } catch (e: IOException) {
        e.printStackTrace()
      }

      if (buflen <= 0) {
        return false
      }
    }
    return true
  }

  private fun readByte(): Int {
    return if (hasNextByte()) buffer[ptr++].toInt() else -1
  }

  private fun isPrintableChar(c: Int): Boolean {
    return 33 <= c && c <= 126
  }

  private fun skipUnprintable() {
    while (hasNextByte() && !isPrintableChar(buffer[ptr].toInt())) ptr++
  }

  operator fun hasNext(): Boolean {
    skipUnprintable()
    return hasNextByte()
  }

  operator fun next(): String {
    if (!hasNext()) throw NoSuchElementException()
    val sb = StringBuilder()
    var b = readByte()
    while (isPrintableChar(b)) {
      sb.appendCodePoint(b)
      b = readByte()
    }
    return sb.toString()
  }

  fun nextLong(): Long {
    if (!hasNext()) throw NoSuchElementException()
    var n: Long = 0
    var minus = false
    var b = readByte()
    if (b == '-'.toInt()) {
      minus = true
      b = readByte()
    }
    if (b < '0'.toInt() || '9'.toInt() < b) {
      throw NumberFormatException()
    }
    while (true) {
      if ('0'.toInt() <= b && b <= '9'.toInt()) {
        n *= 10
        n += (b - '0'.toInt()).toLong()
      } else return if (b == -1 || !isPrintableChar(b)) {
        if (minus) -n else n
      } else {
        throw NumberFormatException()
      }
      b = readByte()
    }
  }
}

data class Edge(val from: Int, val to: Int, val cost: Long)

data class State(val v: Int, val cost: Long)

fun compareState(s1: State, s2: State): Int {
  if (s1.cost > s2.cost) return 1
  if (s1.cost < s2.cost) return -1
  return 0
}

//fun readStrings(s: String): List<String> {
//  val values = mutableListOf<String>()
//  var start = 0
//  for (i in 0 until s.length) {
//    if (s[i] == ' ') {
//      values.add(s.substring(start, i))
//      start = i + 1
//    }
//  }
//  values.add(s.substring(start))
//  return values
//}

fun readIntList(s: String): List<Int> {
  var values = mutableListOf<Int>()
  var count = 0
  var currentInt = 0
  for (i in 0 until s.length) {
    if (s[i] == ' ') {
      values.add(currentInt)
      currentInt = 0
      count++
    } else {
      currentInt *= 10
      currentInt += s[i] - '0'
    }
  }
  values.add(currentInt)
  return values
}


fun main(args: Array<String>) {
  val scanner = FastScanner()
  val n = scanner.nextLong().toInt()
  val m = scanner.nextLong().toInt()
  val s = scanner.nextLong().toInt() - 1
  val t = scanner.nextLong().toInt() - 1
  val graph = Array(n, { mutableListOf<Edge>() })
  repeat(m) {
    // val line = readLine()!!
    // val (uRaw, vRaw, dInt) = readIntList(line)
    val u = scanner.nextLong().toInt() - 1
    val v = scanner.nextLong().toInt() - 1
    val d = scanner.nextLong()
    graph[u].add(Edge(u, v, d))
    graph[v].add(Edge(v, u, d))
  }

  // Dijkstra from s
  val pq = PriorityQueue<State>(11, { s1: State, s2: State -> compareState(s1, s2) })
  val dist = LongArray(n, { Long.MAX_VALUE })
  dist[s] = 0
  pq.add(State(s, 0L))
  while (pq.isNotEmpty()) {
    val state = pq.poll()!!
    if (dist[state.v] < state.cost) continue
    for (e in graph[state.v]) {
      if (state.cost + e.cost < dist[e.to]) {
        dist[e.to] = state.cost + e.cost
        pq.add(State(e.to, state.cost + e.cost))
      }
    }
  }
  if (DEBUG) println("dist: ${dist.toList()}")

  val sGraph = Array(n, { mutableListOf<Int>() })
  val tGraph = Array(n, { mutableListOf<Int>() })

  val stack = ArrayDeque<Int>()
  stack.offerLast(t)
  val visited = BooleanArray(n)
  while (stack.isNotEmpty()) {
    val v = stack.pollLast()
    if (visited[v]) continue
    visited[v] = true
    if (DEBUG) println("v: $v")
    for (e in graph[v]) {
      if (dist[v] == dist[e.to] + e.cost) {
        tGraph[v].add(e.to)
        sGraph[e.to].add(v)
        stack.offerLast(e.to)
      }
    }
  }
//  for (v in 0 until n) {
//    for (e in graph[v]) {
//      if (dist[v] + e.cost == dist[e.to]) {
//        tGraph[e.to].add(v)
//        sGraph[v].add(e.to)
//      }
//    }
//  }
  if (DEBUG) println("sGraph: ${sGraph.toList()}")
  if (DEBUG) println("tGraph: ${tGraph.toList()}")

//  val sCount = Array(n, { FiniteField(0) })
//  sCount[s] = FiniteField(1)
//  val sSorted = dist.withIndex().sortedBy { it.value }.map { it.index }
//  fillCount(s, sGraph, sSorted, sCount)
//  if (DEBUG) println("sCount: ${sCount.toList()}")
//
//  val tCount = Array(n, { FiniteField(0) })
//  tCount[t] = FiniteField(1)
//  val tSorted = sSorted.reversed()
//  fillCount(t, tGraph, tSorted, tCount)
//  if (DEBUG) println("tCount: ${tCount.toList()}")
//
//  var ans = sCount[t] * tCount[s]
//  if (DEBUG) println("ans STEP 1: $ans")
//  val totalDist = dist[t]
//  // Meet on vertex
//  for (v in 0 until n) {
//    if (dist[v] * 2 == totalDist) {
//      ans -= sCount[v] * sCount[v] * tCount[v] * tCount[v]
//    }
//  }
//  if (DEBUG) println("ans STEP 2: $ans")
//
//  // Meet on edge
//  for (v in 0 until n) {
//    for (e in graph[v]) {
//      if (dist[v] + e.cost == dist[e.to] && dist[v] * 2 < totalDist && dist[e.to] * 2 > totalDist) {
//        ans -= sCount[v] * sCount[v] * tCount[e.to] * tCount[e.to]
//      }
//    }
//  }
//  if (DEBUG) println("ans STEP 3: $ans")

  val sCount = LongArray(n, { 0L })
  sCount[s] = 1L
  val sSorted = dist.withIndex().sortedBy { it.value }.map { it.index }
  fillCount(s, sGraph, sSorted, sCount)
  if (DEBUG) println("sCount: ${sCount.toList()}")

  val tCount = LongArray(n, { 0L })
  tCount[t] = 1L
  val tSorted = sSorted.reversed()
  fillCount(t, tGraph, tSorted, tCount)
  if (DEBUG) println("tCount: ${tCount.toList()}")

  var ans = sCount[t] * tCount[s]
  if (DEBUG) println("ans STEP 1: $ans")
  val totalDist = dist[t]
  // Meet on vertex
  for (v in 0 until n) {
    if (dist[v] * 2 == totalDist) {
      val f1 = sCount[v] * sCount[v] % P
      val f2 = tCount[v] * tCount[v] % P
      val delta = f1 * f2 % P
      ans = (ans + P - delta) % P
    }
  }
  if (DEBUG) println("ans STEP 2: $ans")

  // Meet on edge
  for (v in 0 until n) {
    for (e in graph[v]) {
      if (dist[v] + e.cost == dist[e.to] && dist[v] * 2 < totalDist && dist[e.to] * 2 > totalDist) {
        val f1 = sCount[v] * sCount[v] % P
        val f2 = tCount[e.to] * tCount[e.to] % P
        val delta = f1 * f2 % P
        ans = (ans + P - delta) % P
      }
    }
  }
  if (DEBUG) println("ans STEP 3: $ans")

  println(ans)
}

fun fillCount(r: Int, graph: Array<MutableList<Int>>, tSorted: List<Int>, count: LongArray) {
  for (v in tSorted) {
    for (u in graph[v]) {
      count[u] = (count[u] + count[v]) % P
    }
  }
}

Submission Info

Submission Time
Task E - Avoiding Collision
User ymatsux
Language Kotlin (1.0.0)
Score 700
Code Size 7578 Byte
Status AC
Exec Time 1517 ms
Memory 129284 KB

Compile Error

Main.kt:275:15: warning: parameter 'r' is never used
fun fillCount(r: Int, graph: Array<MutableList<Int>>, tSorted: List<Int>, count: LongArray) {
              ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 700 / 700
Status
AC × 4
AC × 22
Set Name Test Cases
Sample sample01.txt, sample02.txt, sample03.txt, sample04.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, sample01.txt, sample02.txt, sample03.txt, sample04.txt
Case Name Status Exec Time Memory
01.txt AC 1292 ms 108008 KB
02.txt AC 1212 ms 106276 KB
03.txt AC 1447 ms 122788 KB
04.txt AC 1413 ms 119888 KB
05.txt AC 1268 ms 109420 KB
06.txt AC 1344 ms 118072 KB
07.txt AC 1414 ms 123668 KB
08.txt AC 1234 ms 114008 KB
09.txt AC 1401 ms 118988 KB
10.txt AC 1423 ms 120524 KB
11.txt AC 1449 ms 116608 KB
12.txt AC 1365 ms 122416 KB
13.txt AC 1432 ms 118788 KB
14.txt AC 1456 ms 122576 KB
15.txt AC 1402 ms 117932 KB
16.txt AC 1412 ms 124796 KB
17.txt AC 1380 ms 120484 KB
18.txt AC 1517 ms 129284 KB
sample01.txt AC 207 ms 35852 KB
sample02.txt AC 207 ms 35812 KB
sample03.txt AC 207 ms 33948 KB
sample04.txt AC 210 ms 35828 KB