Submission #1518225


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)
        }
      }
    }
    val list1g = len1.filter(x => x <= lenST).groupBy(x => x)
    val list2g = len2.filter(x => x <= lenST).groupBy(x => x)
    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 1505 Byte
Status MLE
Exec Time 1406 ms
Memory 128392 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 337 ms 25400 KB
00-sample2.txt AC 336 ms 25392 KB
00-sample4.txt AC 337 ms 25412 KB
50-random10.txt AC 341 ms 25384 KB
50-random11.txt AC 333 ms 25520 KB
50-random12.txt AC 338 ms 25284 KB
50-random13.txt AC 338 ms 25284 KB
50-random14.txt AC 336 ms 25392 KB
50-random15.txt AC 335 ms 25280 KB
50-random16.txt AC 333 ms 27344 KB
50-random17.txt AC 334 ms 25388 KB
50-random18.txt AC 339 ms 25384 KB
50-random19.txt AC 341 ms 25656 KB
50-random20.txt AC 336 ms 25380 KB
50-random21.txt AC 338 ms 25524 KB
50-random22.txt AC 344 ms 25672 KB
50-random23.txt AC 337 ms 25424 KB
50-random24.txt AC 335 ms 25536 KB
50-random25.txt AC 337 ms 25404 KB
50-random26.txt AC 337 ms 25536 KB
50-random27.txt AC 337 ms 23596 KB
50-random28.txt AC 337 ms 25284 KB
50-random29.txt AC 337 ms 25532 KB
50-random30.txt AC 342 ms 25404 KB
50-random31.txt AC 338 ms 25408 KB
50-random32.txt AC 339 ms 25400 KB
50-random33.txt AC 350 ms 25388 KB
50-random34.txt AC 356 ms 23624 KB
50-random35.txt AC 345 ms 25280 KB
50-random36.txt AC 357 ms 25792 KB
50-random37.txt AC 353 ms 25784 KB
50-random38.txt AC 356 ms 25652 KB
50-random39.txt AC 343 ms 25400 KB
50-random40.txt AC 508 ms 30792 KB
50-random41.txt AC 397 ms 26056 KB
50-random42.txt AC 419 ms 28040 KB
50-random43.txt AC 357 ms 25792 KB
50-random44.txt AC 426 ms 28652 KB
50-random45.txt AC 347 ms 25412 KB
50-random46.txt AC 447 ms 30120 KB
50-random47.txt AC 447 ms 28652 KB
50-random48.txt AC 457 ms 28836 KB
50-random49.txt AC 470 ms 29016 KB
50-random50.txt AC 643 ms 37908 KB
50-random51.txt AC 724 ms 39688 KB
50-random52.txt AC 558 ms 35924 KB
50-random53.txt AC 755 ms 39244 KB
50-random54.txt AC 759 ms 40168 KB
50-random55.txt AC 793 ms 39184 KB
50-random56.txt AC 451 ms 28424 KB
50-random57.txt AC 633 ms 38016 KB
50-random58.txt AC 658 ms 37844 KB
50-random59.txt AC 599 ms 38204 KB
50-random60.txt AC 1122 ms 80276 KB
50-random61.txt AC 900 ms 78700 KB
50-random62.txt MLE 1122 ms 117648 KB
50-random63.txt AC 993 ms 75984 KB
50-random64.txt AC 1082 ms 81040 KB
50-random65.txt AC 865 ms 52164 KB
50-random66.txt AC 1001 ms 53452 KB
50-random67.txt AC 809 ms 40584 KB
50-random68.txt AC 698 ms 39168 KB
50-random69.txt AC 621 ms 36368 KB
intoverflow00.txt MLE 1371 ms 127704 KB
intoverflow01.txt MLE 1395 ms 126080 KB
intoverflow02.txt MLE 1363 ms 125924 KB
intoverflow03.txt MLE 1379 ms 126140 KB
intoverflow04.txt MLE 1380 ms 126392 KB
intoverflow05.txt MLE 1388 ms 128264 KB
intoverflow06.txt MLE 1406 ms 126560 KB
intoverflow07.txt MLE 1385 ms 127552 KB
intoverflow08.txt MLE 1399 ms 128392 KB
intoverflow09.txt MLE 1372 ms 126184 KB