mirzaf's blog

CSES, Graph Algorithms: Monsters.
By mirzaf, history, 3 years ago, In English

Problem Link: https://cses.fi/problemset/task/1194

The idea was actually pretty straightforward, just an implementation of multisource BFS (160+ lines).

My submission is still TLE on one test case (19th test case), and the rest were AC. Still can't figure it out.

Here's my submission, perhaps someone out there is willing to give a hand. Language: C++ 17. https://cses.fi/paste/233c9c55d599a6ba247883/

Cheers^_^

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't think you needed to use a map for storing parents which adds log(n) factor to complexity instead you can use a simple array and the idea is not to use coordinates of the cell as pair but convert them into linear ids using a simple hash function. Here is an implementation using the same. link to code.

Hope this is helpful to you.

cheers^_^

→ Reply