Codeforces Round 884 E. Great Grids

E. Great Grids

题意

一个 $\times m$ 的网格图是 $g oo d$ 的当且仅当：

每个网格的字符是 $A 、 B 、 C$ 中的一种
每一个 $\times 2$ 的子格都包含三种不同的字符
相邻的格子字符不一样

现在给定 $k$ 个限制条件，每个限制条件约定：
$x_1,y_1)$ 和 $x_2,y_2)$ 的字符一样，并且这两个格子是对角格

问满足所有约束条件的 $g oo d$ 网格图是否存在

题意

观察发现：每一个 $\times 2$ 的子格，它的其中一对对角格一定相同，另外一对对角格一定不同。我们先把三种字符转化成数字： $0 、 1 、 2$ ，然后我们在每个格子画一个向右和向下的箭头，权值为相邻数字的权值差模 $3$ 。

例如：
$\rarr b$
$\darr \hspace{15pt} \darr$
$\rarr c$

转化成：
$\stackrel{2} \rarr 1$
$\darr \stackrel{2} {} \hspace{15pt} \darr \stackrel{2} {}$
$\stackrel{2} \rarr 2$

上面这个摆放方式很特殊，因为这是其中一种情况：右上和左下是相等字符，如果是另外一个对角格是相等的，横线和竖线就不相等。但是不管是哪个对角格相等，同一列的横线之间的边权一定是相等的，同理，同一行的竖线的边权也是相等的。

证明：假设相同的数字是 $x$ ，另外两个数字是 $x_1$ 和 $x_2$ ，并且假设相等的对角格是右上和左下（另外一种情况也是对称），那么：
$\quad (x_1 - x) \equiv (x - x_2) \quad (mod 3)$
$\Leftrightarrow x_1 + x_2 \equiv 2x \quad (mod 3)$
$\Leftrightarrow x_1 + x_2 \equiv 2(3 - (x_1 + x_2)) \quad (mod 3)$
$\Leftrightarrow x_1 + x_2 \equiv 6 - 2(x_1 + x_2) \quad (mod 3)$
$\Leftrightarrow 3(x_1 + x_2) \equiv 6 \quad (mod 3)$
可以发现：同余式两边都是 $0$ ，显然同余

其他情况也可以类比出来。
那么现在我们一共有 $n - 1$ 条竖线， $m - 1$ 条横线，也就是一共 $n + m - 2$ 个变量。
如果相等的对角格是右上左下这种情况，那么对应的横线和竖线边权相等，
另外一种情况就是不等。

因此对于 $k$ 个限制条件，我们建立相应的边，跑 $2_SAT$ 或二分图染色就可以得出答案

#include<bits/stdc++.h>
#define fore(i,l,r)	for(int i=(int)(l);i<(int)(r);++i)
#define fi first
#define se second
#define endl '\n'
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr << #x << " = " << x << ed;

const int INF=0x3f3f3f3f;
const long long INFLL=1e18;

typedef long long ll;

std::vector<int> sccno;
std::vector<std::vector<int>> g;
int D;
std::vector<int> low;
std::vector<int> dfn;
int tot;
std::stack<int> st;
int n, m, k;

void Tarjan(int u){
    st.push(u);
    dfn[u] = low[u] = ++tot;
    for(auto v : g[u])
        if(!dfn[v]){
            Tarjan(v);
            low[u] = std::min(low[u], low[v]);
        }
        else if(!sccno[v]) low[u] = std::min(low[u], dfn[v]);
    if(low[u] == dfn[u]){
        ++tot;
        while(true){
            int v = st.top();
            st.pop();
            sccno[v] = tot;
            if(v == u) break;
        }
    }
}

bool two_sat(){
    fore(i, 1, 2 * (n + m - 2) + 1)
        if(!dfn[i])
            Tarjan(i);
    fore(i, 1, n + m - 1)
        if(sccno[i] == sccno[i + D])
            return false;
    return true;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int t;
    std::cin >> t;
    while(t--){
        std::cin >> n >> m >> k;
        sccno.assign(2 * (n + m + 5), 0);
        g.assign(2 * (n + m + 5), std::vector<int>());
        low.assign(2 * (n + m + 5), 0);
        dfn.assign(2 * (n + m + 5), 0);
        tot = 0;
        D = n + m - 2;
        while(k--){
            int x1, y1, x2, y2;
            std::cin >> x1 >> y1 >> x2 >> y2;
            if(y1 + 1 == y2){
                int u = x1, v = n - 1 + y1;
                g[u].push_back(v + D);
                g[v].push_back(u + D);
                g[u + D].push_back(v);
                g[v + D].push_back(u);
            }
            else{
                int u = x1, v = n - 1 + y2;
                g[u].push_back(v);
                g[v].push_back(u);
                g[u + D].push_back(v + D);
                g[v + D].push_back(u + D);
            }
        }
        std::cout << (two_sat() ? "YES" : "NO") << endl;
    }
    return 0;
}