Submission #1518222


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(next) = len1(now) + 1
          que1.enqueue(next)
        }
      }
    }
    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(next) = len2(now) + 1
          que2.enqueue(next)
        }
      }
    }
    val list1g = len1.groupBy(x => x)
    val list2g = len2.groupBy(x => x)
    val lenST = len1(T) - 2
    var ans = 0
    for (i <- 0 to lenST) {
      val j = lenST - i
      ans += list1g(i).length * list2g(j).length
    }
    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 1403 Byte
Status MLE
Exec Time 1390 ms
Memory 128044 KB

Judge Result

Set Name All
Score / Max Score 0 / 100
Status
AC × 63
MLE × 10
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 344 ms 25532 KB
00-sample2.txt AC 342 ms 25536 KB
00-sample4.txt AC 334 ms 25396 KB
50-random10.txt AC 336 ms 25408 KB
50-random11.txt AC 342 ms 25252 KB
50-random12.txt AC 333 ms 25280 KB
50-random13.txt AC 338 ms 23628 KB
50-random14.txt AC 344 ms 25420 KB
50-random15.txt AC 338 ms 25376 KB
50-random16.txt AC 338 ms 25532 KB
50-random17.txt AC 333 ms 25404 KB
50-random18.txt AC 333 ms 25296 KB
50-random19.txt AC 340 ms 25396 KB
50-random20.txt AC 335 ms 25272 KB
50-random21.txt AC 337 ms 25400 KB
50-random22.txt AC 338 ms 25536 KB
50-random23.txt AC 337 ms 25372 KB
50-random24.txt AC 332 ms 25504 KB
50-random25.txt AC 338 ms 25440 KB
50-random26.txt AC 338 ms 25404 KB
50-random27.txt AC 335 ms 25380 KB
50-random28.txt AC 448 ms 23496 KB
50-random29.txt AC 349 ms 25372 KB
50-random30.txt AC 338 ms 25288 KB
50-random31.txt AC 338 ms 25508 KB
50-random32.txt AC 343 ms 25524 KB
50-random33.txt AC 350 ms 25940 KB
50-random34.txt AC 360 ms 27452 KB
50-random35.txt AC 339 ms 25420 KB
50-random36.txt AC 361 ms 25672 KB
50-random37.txt AC 361 ms 25664 KB
50-random38.txt AC 358 ms 23484 KB
50-random39.txt AC 347 ms 25400 KB
50-random40.txt AC 536 ms 31076 KB
50-random41.txt AC 411 ms 27844 KB
50-random42.txt AC 434 ms 28296 KB
50-random43.txt AC 370 ms 25792 KB
50-random44.txt AC 445 ms 28248 KB
50-random45.txt AC 352 ms 25500 KB
50-random46.txt AC 454 ms 28240 KB
50-random47.txt AC 458 ms 28688 KB
50-random48.txt AC 494 ms 29052 KB
50-random49.txt AC 483 ms 27224 KB
50-random50.txt AC 752 ms 38048 KB
50-random51.txt AC 837 ms 40744 KB
50-random52.txt AC 587 ms 37444 KB
50-random53.txt AC 833 ms 39500 KB
50-random54.txt AC 851 ms 39384 KB
50-random55.txt AC 835 ms 48672 KB
50-random56.txt AC 458 ms 26256 KB
50-random57.txt AC 770 ms 39116 KB
50-random58.txt AC 735 ms 38336 KB
50-random59.txt AC 679 ms 38904 KB
50-random60.txt AC 1176 ms 80340 KB
50-random61.txt AC 1082 ms 82552 KB
50-random62.txt AC 1272 ms 116280 KB
50-random63.txt AC 1124 ms 82548 KB
50-random64.txt AC 1118 ms 80024 KB
50-random65.txt AC 989 ms 51504 KB
50-random66.txt AC 1020 ms 51980 KB
50-random67.txt AC 912 ms 39684 KB
50-random68.txt AC 792 ms 39404 KB
50-random69.txt AC 761 ms 38500 KB
intoverflow00.txt MLE 1362 ms 126220 KB
intoverflow01.txt MLE 1369 ms 126148 KB
intoverflow02.txt MLE 1337 ms 125824 KB
intoverflow03.txt MLE 1370 ms 127408 KB
intoverflow04.txt MLE 1356 ms 126148 KB
intoverflow05.txt MLE 1331 ms 126108 KB
intoverflow06.txt MLE 1371 ms 126016 KB
intoverflow07.txt MLE 1371 ms 127820 KB
intoverflow08.txt MLE 1390 ms 128044 KB
intoverflow09.txt MLE 1333 ms 126236 KB