100mil's blog

If anyone could help me as to why the way I use BFS always ends up getting TLE.
By 100mil, history, 3 years ago, In English

I was solving this problem-https://codeforces.net/problemset/problem/1613/E This is my solution-https://codeforces.net/contest/1613/submission/138713743 Can pls someone tell me what is wrong here.

Tags bfs
  • Vote: I like it
  • +6
  • Vote: I do not like it

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

The problem is in your check function, you are copying a (vector<char> v )and (vector<vector<int>> vis) every time you call check function. To avoid this make v and vis vector global.

→ Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

The problem in this line:

bool check(int i,int j,vector<vector<char>> v,vector<vector<int>> vis)

Your vector<vector<char>> v and vector<vector<int>> vis are copied every time, when you call this function. Instead you should write somthing like: bool check(int i,int j,vector<vector<char>> &v,vector<vector<int>> &vis)

there is your AC solution with this fix 138716320

And write "\n" instead endl, because endl flushing output, what takes time (sorry for my bad english)

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks a lot for helping me! I solved it.

    → Reply