ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1930. Ivan's Car

If you're using BFS :D
Posted by GastonFontenla 2 Aug 2015 15:05
If you are using BFS, use a adjacency list. It's faster for finding the adjacents nodes. You too should use a "direccion list". It has the same size that the adjacency list, but it's filled with boolean values. For example, in the adjacency list of the node 1, you have nodes 2 3 4. If you need to go uphill from 1 to 2, in the correspondant place of the 2, you should write a 1, and if you need to go downhill, a 0. This is how I solved. I was stuck on time limit when I was using the same format of given data, but later I understood that the adjacency list it's very faster than 2 cols matrix (faster, but uses a lot more memory). Good luck, and try all the test posted in discussion.