Hướng dẫn cho Tổ kiến (Chọn ĐT'23-24)
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.
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.
- Subtask 1, 2: Thực hiện thuật toán tìm thành phần liên thông trên mỗi ô trong hình chữ nhật. Độ phức tạp \(O(k⋅q)\).
- Subtask 3: Gọi số đỉnh trong một hình chữ nhật là \(v\) số cạnh kết nối giữa các đỉnh này là \(e\), ta có số thành phần liên thông với đồ thị dạng cây là \(v-e\). Do đó ta chỉ cần tính \(v,e\) là tính được kết quả. Với \(n,m≤3000\) ta có thể dễ dàng tính được \(v,e\) bằng prefix sum 2D.
- Subtask 4: Ta có thuật toán chuẩn như sau:
- Sử dụng DFS dựng thành cây có gốc và định hướng các cạnh từ đỉnh cha xuống đỉnh con
- Với mỗi truy vấn, ta có thể thấy mỗi thành phần liên thông sẽ có xuất phát từ một ô trên cạnh của hình chữ nhật và được định hướng từ một ô bên ngoài hình chữ nhật hướng vào. Ngoại trừ thành phần liên thông có chứa đỉnh gốc của cây thì không có ô nào định hướng vào hình chữ nhật.
- Như vậy ta chỉ cần đếm xem trên 4 cạnh của hình chữ nhật có bao nhiêu ô có định hướng vào và kiểm tra xem gốc của cây có nằm trong hình chữ nhật không là tính được số lượng thành phần liên thông tạo bởi hình chữ nhật đang xét.
- Với mỗi cạnh trên ma trận (tối đa \(2⋅10^5\) cạnh theo chiều ngang vào chiều dọc) ta lưu danh sách các ô có định hướng (lên trên, xuống dưới, sang trái, sang phải) và sắp xếp danh sách, như vậy khi cần đếm số lượng ô có định hướng vào hình chữ nhật ta chỉ cần sử dụng lower_bound để đếm trên 4 danh sách tương ứng với 4 cạnh của hình chữ nhật.
Bình luận