Mạng cảm biến chênh lệch

Buổi 67-68 — Mock IOI Data-structures
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions

Đề bài

Có $N$ biến ẩn $x_1, x_2, \dots, x_N$. Bạn cần xử lý tuần tự $Q$ thao tác thuộc hai loại:

  • 1 u v d: đưa vào ràng buộc $x_v - x_u = d$. Nếu ràng buộc này mâu thuẫn với các ràng buộc đã chấp nhận trước đó, hãy bỏ qua nó và in ra CONFLICT; ngược lại chấp nhận nó và in ra OK.
  • 2 u v: nếu từ các ràng buộc đã chấp nhận có thể xác định duy nhất hiệu $x_v - x_u$, in ra giá trị đó; ngược lại in ra UNKNOWN.

Dữ liệu vào

  • Dòng đầu chứa hai số nguyên $N, Q$ ($1 \le N \le 10^5$, $1 \le Q \le 2 \cdot 10^5$).
  • $Q$ dòng tiếp theo, mỗi dòng mô tả một thao tác 1 u v d ($1 \le u, v \le N$, $|d| \le 10^9$) hoặc 2 u v ($1 \le u, v \le N$).

Kết quả

Với mỗi thao tác, in ra kết quả tương ứng trên một dòng.

Subtasks

  • Subtask 1 (25%): $N \le 500$, $Q \le 2000$.
  • Subtask 2 (25%): Toàn bộ thao tác loại 1 đứng trước thao tác loại 2 và không có CONFLICT.
  • Subtask 3 (50%): Không có ràng buộc thêm.

Ví dụ

Input Output
4 6
1 1 2 5
1 2 3 3
2 1 3
1 1 3 10
2 1 4
2 3 1
OK
OK
8
CONFLICT
UNKNOWN
-8
Draft saved