Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lời giải: Hầm Ngục Hogwarts
Hướng tiếp cận
Bài toán yêu cầu kiểm tra xem có đường đi từ mặt đáy () đến mặt trần () thông qua các buồng hình cầu. Đây là bài toán kiểm tra tính liên thông trong đồ thị.
Nhận xét quan trọng
Mô hình hóa đồ thị: Mỗi buồng là một đỉnh. Hai buồng và có cạnh nối nếu khoảng cách giữa tâm , tức là: Bình phương hai vế để tránh số thực:
Nút ảo: Thêm nút ảo "đáy" nối với mọi buồng có , và nút ảo "trần" nối với mọi buồng có .
Tránh tràn số: Tọa độ lên đến , nên hiệu bình phương lên đến . Tổng 3 bình phương lên đến , và lên đến . Cả hai đều nằm trong phạm vi
long long().
Thuật toán
Sử dụng Union-Find (Disjoint Set Union) hoặc BFS/DFS:
- Tạo đỉnh: buồng + 1 nút đáy + 1 nút trần.
- Duyệt mọi buồng :
- Nếu : nối buồng với nút đáy.
- Nếu : nối buồng với nút trần.
- Duyệt mọi cặp buồng : nếu khoảng cách bình phương , nối với .
- Kiểm tra xem nút đáy và nút trần có cùng thành phần liên thông hay không.
Độ phức tạp
- Thời gian: với là hàm Ackermann ngược (gần như hằng số).
- Bộ nhớ: .
- Với và , tổng thao tác , hoàn toàn đủ nhanh.
https://oj.chuyentin.pro/problem/cheese/editorial
Bình luận