GFSSOC '14 Winter J5 - Pursuit of Knowledge

Points: 10 (partial)

Time limit: 2.0s

Memory limit: 64M

Authors:

Problem type

The programming club at Don Mills has been booming lately, and so Griffy has decided to install a system to figure out the path that students should take to reach the club room (which is not necessarily held in the same room every time). He hopes that this act of kindness will weaken Timothy Li's defenses so he will be able to beat him up at tic-tac-toe. There are $N$ ~N~ rooms numbered from $1$ ~1~ to $N$ ~N~, and $M$ ~M~ one-way hallways that connect two locations. Each hallway takes $T$ ~T~ minutes to traverse. Given $Q$ ~Q~ queries in the form a b, where $a$ ~a~ is not equal to $b$ ~b~, find the least amount of time needed to go from room $a$ ~a~ to room $b$ ~b~. If it is not possible to get from $a$ ~a~ to $b$ ~b~, output Not enough hallways!.

Input Specification

First line, three integers $N$ ~N~ $(2 \le N \le 1\,000)$ ~(2 \le N \le 1\,000)~, $M$ ~M~ $(0 \le M \le 1\,000)$ ~(0 \le M \le 1\,000)~, $T$ ~T~ $(1 \le T \le 1\,000)$ ~(1 \le T \le 1\,000)~.

Next $M$ ~M~ lines, two integers a b on each line describing a one-way hallway from $a$ ~a~ to $b$ ~b~.

Line $M+2$ ~M+2~, one integer $Q$ ~Q~ $(1 \le Q \le 200\,000)$ ~(1 \le Q \le 200\,000)~.

Lines $M+3 \dots M+2+Q$ ~M+3 \dots M+2+Q~, two integers a b the query rooms.

Output Specification

One line for each query, the shortest amount of time taken to go from room $a$ ~a~ to room $b$ ~b~.

Sample Input

Sample Output

8
Not enough hallways!
24

Comments

0

andrewtam commented on Aug. 19, 2020, 8:29 p.m. ← edit 4 →

Can someone please take a look at my code. I'm getting TLE on the last test case and I'm not sure why. Edit - NVM I found my problem: for anyone else attempting this problem, note that $M$ ~M~ is far less than $N^2$ ~N^2~. Therefore an adjacency list is more efficient than an adjacency matrix.

2

institutionalisation commented on Nov. 20, 2017, 1:44 a.m. ← edit 2 →

I don't see why I'm getting WA. Help?

edit: I was invoking undefined behaviour. Thanks.

3

Ninjaclasher commented on Nov. 20, 2017, 3:26 a.m.

There's something really sketchy when you call g() while reading in the edges (perhaps undefined behaviour). Change it to how you would normally read in edges and it ACs.

3

aeternalis1 commented on July 29, 2017, 5:29 p.m.

What's slowing down my code?

I used BFS to find all connected rooms and stored each room and time in separate answer arrays. I used the fastest input method and managed to AC all the test cases but the last one. What can I make faster?

2

wleung_bvg commented on July 29, 2017, 6:47 p.m. ← edited →

Each of your queries takes linear time to answer (not much faster than BFS itself). Try to find a way to store your answers so you can answer queries in constant time.

3

aeternalis1 commented on July 29, 2017, 7:26 p.m.

I did as you suggested and stored the answers in a single, larger array within which the value of the second query room was the index for the time it took to get there, but I still TLE'd the last case.

2

wleung_bvg commented on July 29, 2017, 11:07 p.m.

Try modifying your BFS function to use only 1 for loop instead of 2

2

aeternalis1 commented on July 30, 2017, 3:13 p.m.

You've already solved this in python, correct? Are there any significant differences in our approaches to the question?

1

Pleedoh commented on July 30, 2017, 4:42 p.m.

Remember to try submitting a few times, as the grading speed is inconsistent. It is totally possible to TLE one time and then AC with the exact same code another.

2

wleung_bvg commented on July 30, 2017, 4:32 p.m.

Our approaches are mostly the same. The main difference is the way we programmed the BFS function. Honestly, I'm not sure why your code is TLEing.

2

aeternalis1 commented on July 29, 2017, 11:32 p.m.

I don't think the double for loop really has much effect on the overall runtime because the first for loop just makes sure that all of the rooms at that breadth are checked at the same time. It runs through all the items in the queue just as it would without the for loop.

2

Pleedoh commented on July 29, 2017, 11:50 p.m. ← edited →

I think you're over thinking this, you have so many variables that you just don't need.

2

wleung_bvg commented on July 29, 2017, 11:41 p.m.

It won't affect the overall time complexity, but might help with constant optimization

2

aeternalis1 commented on July 29, 2017, 11:51 p.m.

TLE'd again. I think the issue may lie in how I'm currently running the BFS from each source node, but idk anymore.

2

Pleedoh commented on July 29, 2017, 11:57 p.m.

Use a source node, pop in the connected nodes, sift through the connected to that connected (friends of friends) and say the distance from the source to the friend of friend is just 1 more.

2

Pleedoh commented on July 29, 2017, 7:44 p.m. ← edited →

Given that the time limit is two seconds, try something like floyd?

2

wleung_bvg commented on July 29, 2017, 10:46 p.m. ← edited →

Floyd takes $V^3$ ~V^3~ time and might TLE in Python. Doing BFS from every room and storing the answers in a 2D array should be sufficient enough.

2

Pleedoh commented on July 29, 2017, 11:07 p.m. ← edited →

Floyd's will not TLE in C++, for me the longest case took just under 0.6 seconds. The BFS solution is clearly better though, and I will try it now!

27

LOLWHATOMGBBQ commented on Dec. 9, 2014, 12:30 a.m.

What kind of hallways are unidirectional?

10

Xyene commented on Dec. 9, 2014, 1:06 a.m. ← edited →

Sketchy DMCI hallways.

2

awaykened commented on Dec. 9, 2014, 12:32 a.m.

"gates of truth"