Why does this BFS approach to Round 847 Problem F TLE?

Revision en1, by ersahinceumut, 2023-02-01 23:55:54

Here is the problem: 1790F - Тимофей и черно-белое дерево

Here is the idea behind the solution: We add black nodes to the tree one by one, each time calling a BFS starting on the newly added black node in order to find the closest black node. If the path we find is smaller than the previous answer, we update accordingly. I also implemented an optimization where if the BFS depth exceeds the previous smallest path length, we stop the BFS.

My question is why / in what type of test case does this TL? I tried some randomized tests on $$$2\cdot10^5$$$ nodes but couldn't find a TL.

Here is my implementation of said solution: 191442467


  Rev. Lang. By When Δ Comment
en2 English ersahinceumut 2023-02-01 23:58:05 0 (published)
en1 English ersahinceumut 2023-02-01 23:55:54 686 Initial revision (saved to drafts)