Mạng cảm biến chênh lệch
Points
85
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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 raCONFLICT; ngược lại chấp nhận nó và in raOK.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 raUNKNOWN.
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ặc2 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ại2và 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 |
Community Discussion