#P4782. 【模板】2-SAT 问题

    ID: 91 远端评测题 1000ms 512MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>图论Special JudgeO2优化2-SAT强连通分量,缩点

【模板】2-SAT 问题

题目描述

nn 个布尔变量 x1x_1\simxnx_n,另有 mm 个需要满足的条件,每个条件的形式都是 「xix_itrue / falsexjx_jtrue / false」。比如 「x1x_1 为真或 x3x_3 为假」、「x7x_7 为假或 x2x_2 为假」。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

输入格式

第一行两个整数 nnmm,意义如题面所述。

接下来 mm 行每行 44 个整数 ii, aa, jj, bb,表示 「xix_iaaxjx_jbb」(a,b{0,1}a, b\in \{0,1\})

输出格式

如无解,输出 IMPOSSIBLE;否则输出 POSSIBLE

下一行 nn 个整数 x1xnx_1\sim x_nxi{0,1}x_i\in\{0,1\}),表示构造出的解。

3 1
1 1 3 0
POSSIBLE
0 0 0

提示

1n,m1061\leq n, m\leq 10^6 , 前 33 个点卡小错误,后面 55 个点卡效率。

由于数据随机生成,可能会含有( 10 0 10 0)之类的坑,但按照最常规写法的写的标程没有出错,各个数据点卡什么的提示在标程里。