Hệ thống công tắc
Points
80
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Một hệ thống điều khiển gồm $N$ công tắc nhị phân $x_1, x_2, \dots, x_N$, mỗi công tắc có trạng thái true hoặc false. Hệ thống có $M$ điều kiện an toàn, mỗi điều kiện có dạng $(a \lor b)$, trong đó $a$ và $b$ là các biến hoặc phủ định của chúng.
Một số nguyên dương $k$ đại diện cho $x_k = \text{true}$, còn $-k$ đại diện cho $x_k = \text{false}$. Hãy kiểm tra xem có tồn tại một cách thiết lập trạng thái cho $N$ công tắc để thỏa mãn đồng thời cả $M$ điều kiện hay không.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $N, M$ ($1 \le N \le 10^5$, $1 \le M \le 2 \cdot 10^5$).
- $M$ dòng tiếp theo, mỗi dòng chứa hai số nguyên khác $0$ là $a, b$ ($1 \le |a|, |b| \le N$).
Kết quả
In ra YES nếu tồn tại cách thiết lập thỏa mãn, ngược lại in ra NO.
Subtasks
- Subtask 1 (25%): $N \le 20$.
- Subtask 2 (35%): $N \le 2000$.
- Subtask 3 (40%): Không có ràng buộc thêm.
Ví dụ
| Input | Output |
|---|---|
| 3 4 1 2 -1 3 -2 -3 1 -3 |
YES |
Community Discussion