Hướng dẫn cho Covid'19 (DHBB CT)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: admin

  • Tạo thêm \(m * n\) đỉnh ảo \(x_1....x_{m * n}\) và \(m * n\) đỉnh \(y_1....y_{m * n}\)
  • xét các ô trong bảng, thêm cạnh nối giữa những ô kề nhau.
  • thêm cung từ \(ô(i,j)\) đến \(xa(i,j)\) nếu \(a(i,j) <= m*n\)
  • thêm cung từ \(xa(i,j)\) đến \(ya(i,j)\)
  • thêm cung từ \(ya(i,j)\) đến các \(ô(u,v)\) với \(u * v=a(i,j)\) (Có tối đa \(m * n*log(m*n)\) cung như vậy).
  • Sau đó với mỗi truy vấn ta sẽ dùng thuật toán BFS để đi từ \(ô(p_k,q_k)\) đến \(ô(r_k,s_k)\).

Đpt: \(O(k * m*n*log(m*n))\)

Lời giải của BTC cuộc thi


Bình luận