Solutions of 23 path

Solutions of 23 path - MarisaOJ: Marisa Online Judge

Select solution language

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})$ .