Editorial for CTU Open Contest 2018 - Security Guards - DMOJ: Modern Online Judge

Editorial for CTU Open Contest 2018 - Security Guards

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Fill the $5000 \times 5000$ ~5000 \times 5000~ grid with the distance to the nearest guard.
Use BFS with multiple starts.
Query in constant time.
Complexity $\mathcal O(N^2 + Q)$ ~\mathcal O(N^2 + Q)~

Alternative solution:

Fill the $5000 \times 5000$ ~5000 \times 5000~ grid with $1$ ~1~ on guard positions and $0$ ~0~ otherwise.
Create 2D prefix sum.
For each query, use binary search to get the answer.
Complexity $\mathcal O(N^2 + Q \log N)$ ~\mathcal O(N^2 + Q \log N)~

Comments

There are no comments at the moment.