Submission #1518228


Source Code Expand

import java.util.Scanner

import scala.collection.mutable

object Main {
  def solve(sc: => Scanner): Unit = {
    val N, M = sc.nextInt
    val S, T = sc.nextInt - 1
    val mapping = Array.fill[List[Int]](N)(List())
    for (i <- 0 until M) {
      val x, y = sc.nextInt - 1
      mapping(x).+:=(y)
      mapping(y).+:=(x)
    }
    val len1 = Array.fill[Int](N)(Int.MaxValue / 6)
    len1(S) = 0
    val que1 = mutable.Queue[Int](S)
    while (que1.size != 0) {
      val now = que1.dequeue()
      for (next <- mapping(now)) {
        if (len1(next) > len1(now) + 1 && len1(now) + 1 <= len1(T)) {
          len1(next) = len1(now) + 1
          que1.enqueue(next)
        }
      }
    }
    val lenST = len1(T) - 2
    val len2 = Array.fill[Int](N)(Int.MaxValue / 6)
    len2(T) = 0
    val que2 = mutable.Queue[Int](T)
    while (que2.size != 0) {
      val now = que2.dequeue()
      for (next <- mapping(now)) {
        if (len2(next) > len2(now) + 1 && len2(now) + 1 <= lenST) {
          len2(next) = len2(now) + 1
          que2.enqueue(next)
        }
      }
    }
    var ans = 0
    for (i <- 0 to lenST) {
      val j = lenST - i
      var x = 0
      for (z <- len1) {
        if (z == i) (x += 1)
      }
      var y = 0
      for (z <- len2) {
        if (z == j) (y += 1)
      }
      ans += x * y
    }
    println(ans)
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}

Submission Info

Submission Time
Task B - Minus One
User goryudyuma
Language Scala (2.11.7)
Score 0
Code Size 1511 Byte
Status MLE
Exec Time 1280 ms
Memory 128600 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 62
MLE × 11
Set Name Test Cases
All 00-sample1.txt, 00-sample2.txt, 00-sample4.txt, 50-random10.txt, 50-random11.txt, 50-random12.txt, 50-random13.txt, 50-random14.txt, 50-random15.txt, 50-random16.txt, 50-random17.txt, 50-random18.txt, 50-random19.txt, 50-random20.txt, 50-random21.txt, 50-random22.txt, 50-random23.txt, 50-random24.txt, 50-random25.txt, 50-random26.txt, 50-random27.txt, 50-random28.txt, 50-random29.txt, 50-random30.txt, 50-random31.txt, 50-random32.txt, 50-random33.txt, 50-random34.txt, 50-random35.txt, 50-random36.txt, 50-random37.txt, 50-random38.txt, 50-random39.txt, 50-random40.txt, 50-random41.txt, 50-random42.txt, 50-random43.txt, 50-random44.txt, 50-random45.txt, 50-random46.txt, 50-random47.txt, 50-random48.txt, 50-random49.txt, 50-random50.txt, 50-random51.txt, 50-random52.txt, 50-random53.txt, 50-random54.txt, 50-random55.txt, 50-random56.txt, 50-random57.txt, 50-random58.txt, 50-random59.txt, 50-random60.txt, 50-random61.txt, 50-random62.txt, 50-random63.txt, 50-random64.txt, 50-random65.txt, 50-random66.txt, 50-random67.txt, 50-random68.txt, 50-random69.txt, intoverflow00.txt, intoverflow01.txt, intoverflow02.txt, intoverflow03.txt, intoverflow04.txt, intoverflow05.txt, intoverflow06.txt, intoverflow07.txt, intoverflow08.txt, intoverflow09.txt
Case Name Status Exec Time Memory
00-sample1.txt AC 332 ms 25016 KB
00-sample2.txt AC 331 ms 25120 KB
00-sample4.txt AC 337 ms 25556 KB
50-random10.txt AC 332 ms 25408 KB
50-random11.txt AC 329 ms 25024 KB
50-random12.txt AC 330 ms 25408 KB
50-random13.txt AC 334 ms 27336 KB
50-random14.txt AC 330 ms 27328 KB
50-random15.txt AC 335 ms 25536 KB
50-random16.txt AC 345 ms 25676 KB
50-random17.txt AC 333 ms 23724 KB
50-random18.txt AC 334 ms 25396 KB
50-random19.txt AC 334 ms 25292 KB
50-random20.txt AC 330 ms 25400 KB
50-random21.txt AC 349 ms 25412 KB
50-random22.txt AC 331 ms 25404 KB
50-random23.txt AC 333 ms 25404 KB
50-random24.txt AC 333 ms 25280 KB
50-random25.txt AC 336 ms 25392 KB
50-random26.txt AC 332 ms 25276 KB
50-random27.txt AC 334 ms 25400 KB
50-random28.txt AC 338 ms 25284 KB
50-random29.txt AC 337 ms 25524 KB
50-random30.txt AC 350 ms 25540 KB
50-random31.txt AC 344 ms 25164 KB
50-random32.txt AC 339 ms 25404 KB
50-random33.txt AC 350 ms 25676 KB
50-random34.txt AC 350 ms 27420 KB
50-random35.txt AC 336 ms 25284 KB
50-random36.txt AC 351 ms 25636 KB
50-random37.txt AC 363 ms 25548 KB
50-random38.txt AC 353 ms 25664 KB
50-random39.txt AC 338 ms 25156 KB
50-random40.txt AC 519 ms 31036 KB
50-random41.txt AC 409 ms 27836 KB
50-random42.txt AC 437 ms 28304 KB
50-random43.txt AC 358 ms 25652 KB
50-random44.txt AC 435 ms 28048 KB
50-random45.txt AC 347 ms 25660 KB
50-random46.txt AC 456 ms 28168 KB
50-random47.txt AC 444 ms 28884 KB
50-random48.txt AC 466 ms 29168 KB
50-random49.txt AC 476 ms 29008 KB
50-random50.txt AC 644 ms 38148 KB
50-random51.txt AC 732 ms 44032 KB
50-random52.txt AC 557 ms 35528 KB
50-random53.txt AC 727 ms 41932 KB
50-random54.txt AC 733 ms 40600 KB
50-random55.txt AC 762 ms 49092 KB
50-random56.txt AC 455 ms 28428 KB
50-random57.txt AC 625 ms 38052 KB
50-random58.txt AC 650 ms 38092 KB
50-random59.txt AC 596 ms 37832 KB
50-random60.txt AC 1040 ms 79588 KB
50-random61.txt AC 891 ms 73904 KB
50-random62.txt MLE 1121 ms 117596 KB
50-random63.txt AC 1006 ms 78320 KB
50-random64.txt AC 1003 ms 88724 KB
50-random65.txt AC 854 ms 53444 KB
50-random66.txt AC 886 ms 54332 KB
50-random67.txt AC 766 ms 43236 KB
50-random68.txt AC 696 ms 38764 KB
50-random69.txt AC 631 ms 37792 KB
intoverflow00.txt MLE 1244 ms 125396 KB
intoverflow01.txt MLE 1253 ms 128568 KB
intoverflow02.txt MLE 1268 ms 127076 KB
intoverflow03.txt MLE 1259 ms 126932 KB
intoverflow04.txt MLE 1245 ms 127752 KB
intoverflow05.txt MLE 1268 ms 128088 KB
intoverflow06.txt MLE 1273 ms 128600 KB
intoverflow07.txt MLE 1260 ms 127716 KB
intoverflow08.txt MLE 1280 ms 126632 KB
intoverflow09.txt MLE 1261 ms 126996 KB