Chênh lệch điện thế

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

Có $N$ điểm đo điện thế được đánh số từ $1$ đến $N$ (giá trị điện thế ban đầu chưa biết). Có $Q$ thao tác:

  • 1 u v d: Ghi nhận thông tin $V_u - V_v = d$. Nếu thông tin này mâu thuẫn với các thông tin hợp lệ trước đó, bỏ qua thông tin này và in ra CONFLICT. Ngược lại, không in gì.
  • 2 u v: Hỏi giá trị $V_u - V_v$. Nếu có thể suy ra từ các thông tin hợp lệ trước đó, in ra giá trị đó; ngược lại in ra UNKNOWN.
Dữ liệu vào
  • Dòng đầu tiên chứa hai số nguyên $N, Q$ ($1 \le N, Q \le 10^5$).
  • $Q$ dòng tiếp theo chứa các truy vấn ($|d| \le 10^9$).
Dữ liệu ra
  • In ra kết quả tương ứng cho các truy vấn bị CONFLICT ở loại 1 và cho tất cả truy vấn loại 2.
Ví dụ
Input Output
3 5
1 1 2 5
1 2 3 3
2 1 3
1 1 3 10
2 1 3
8
CONFLICT
8
Giới hạn
  • $1 \le N, Q \le 10^5, |d| \le 10^9$
Draft saved