Register | Login

Solutions of 23 path

Select solution language All Tiếng Việt English Other

Write solution here.

---

pt48583994    Created at    3 likes

Nhận xét: bài toán thực ra là bài toán sau đây: * Cho đồ thị $m$ cạnh $n$ đỉnh, trên mỗi cạnh có 2 số $a$ và $b$. Cho $q$ truy vấn: $u\ v\ A\ B$, kiểm tra xem có 1 cách để từ $u$ đi đến $v$ mà $\max(a)=A$ và $\max(b)=B$ hay không. Có thể có cạnh lặp. Ta có thể biến đổi điều kiện như sau: * Xét đồ thị chứa các cạnh mà $a\leq A$ và $b\leq B$ : * $u$ và $v$ cùng TPLT. * $\max(a)$ trong TPLT của $u$ phải là $A$. * $\max(b)$ trong TPLT của $u$ phải là $B$. Sắp xếp các cạnh và truy vấn theo $b$. Ta duyệt qua từng block cạnh, sử dụng sweepline để duyệt theo $a$ với các cạnh nằm trước block đang xét. Với các cạnh nằm trong block, ta sẽ sử dụng DSU rollback để xử lý. ĐPT: $O(q\log(n)\sqrt{m})$.