Блог пользователя code.degub

0-1 bfs Getting TLE Please help
Автор code.degub, история, 3 года назад, По-английски

Question In this question i am trying to use 0-1 bfs here is my code 115034044 can anyone help me to find why i am getting TLE or what's wrong in this please help

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Oh lol I tried a number of optimizations before I realized that your complexity is $$$\mathcal O(nmk)$$$ with $$$n, m, k \leq 1000$$$, which is too much.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks but 38798575 isn't this submission same ?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That looks like an unintended solution, considering editorial says $$$\mathcal O(nmk)$$$ is supposed to be too slow. Java is considerably slower, so I'd be surprised if you can get the solution to fit.

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

your solution is correct 115077277 , I only added the line if(dis[nr][nc] < dis[cr][cc]+1)break; in your bfs . if you meet a cell that has distance less than distance your current cell +1,then you don't need to consider further since it can never be worse if you started traversing in the same direction from that cell instead .I think this simple optimization makes it O(nm) but I am not sure how to prove it

→ Ответить