Hành trình giới hạn tải trọng

Buổi 25 — Disjoint Set Union Data-structures Graphs sorting
Points
28
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
ds
Submissions
Đề bài

Cho đồ thị vô hướng gồm $N$ đỉnh và $M$ cạnh, cạnh thứ $i$ nối $u_i$ và $v_i$ có trọng số $w_i$. Có $Q$ truy vấn, mỗi truy vấn gồm ba số $s, t, W$: hỏi có tồn tại đường đi từ $s$ đến $t$ chỉ sử dụng các cạnh có trọng số $\le W$ hay không?

Dữ liệu vào
  • Dòng đầu tiên chứa ba số nguyên $N, M, Q$ ($1 \le N, M, Q \le 10^5$).
  • $M$ dòng tiếp theo, mỗi dòng chứa $u_i, v_i, w_i$ ($1 \le u_i, v_i \le N, 1 \le w_i \le 10^9$).
  • $Q$ dòng tiếp theo, mỗi dòng chứa $s, t, W$ ($1 \le s, t \le N, 0 \le W \le 10^9$).
Dữ liệu ra
  • Gồm $Q$ dòng, mỗi dòng in YES hoặc NO.
Ví dụ
Input Output
4 4 3
1 2 5
2 3 10
3 4 3
1 4 8
1 3 8
1 3 10
1 4 7
YES
YES
NO
Giới hạn
  • $1 \le N, M, Q \le 10^5$
Draft saved