GlobeX Cup '18 J5 - Errands

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 128M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

Dereck lives in a city consisting of N houses number from 1 to N. These N houses are connected by M two-way roads.

Dereck is a very busy person. He has Q errands to run for his master, Derek. For each errand, he picks something up from house a and must deliver it to house b. However, Derek is suspicious that Dereck is not taking the shortest path from a to b. Thus, Derek wants Dereck to go through house C for each errand, so that Derek can make sure that Dereck is taking the shortest path.

Derek, being the very smart person he is, knows that going through house C for each errand may result in Dereck not taking the shortest path from house a to b. Thus, Derek wants Dereck to take the shortest path from a to C, and then the shortest path from C to b.

Dereck, not being very good at finding the shortest path, wants you to help him find the shortest path for each errand.

Input Specification

The first line will contain four integers, N, M, Q, C\ (1 \le N \le 10^5, 1 \le M \le 2 \times 10^5, 1 \le Q \le 10^5, 1 \le C \le N), which represents the number of houses, the number of roads, the number of errands, and the house that Dereck must go through for each errand, respectively.

The next M lines will each contain two integers, u, v\ (1 \le u, v \le N), meaning that house u and house v are connected by a single road of length 1. Note that there may be more than one road between any two neighbourhoods.

The next Q lines will each contain two integers, a, b\ (1 \le a, b \le N), meaning that Dereck picks something up at a and must deliver it to b.

Output Specification

For each errand, print the shortest path from house a to house b for Dereck, under the constraint that he must pass through house C. If it is impossible, print This is a scam!.


Subtask 1 [5%]

N, M, Q \le 100

Subtask 2 [25%]

C = 1

Subtask 3 [70%]

No further constraints.

Sample Input

6 7 4 1
1 2
1 3
1 4
2 3
3 4
6 5
5 5
1 4
3 4
5 6
5 5

Sample Output

This is a scam!
This is a scam!


  • -2
    KevinLiu1010  commented on Feb. 18, 2019, 11:16 p.m.

    I'm only running one BFS yet I'm still TLE... Can someone help me?

    • 2
      Arman_Lamei  commented on Aug. 16, 2019, 9:45 p.m. edited

      Use an ArrayList instead of a HashMap for adjacency list. It's much faster.