1844E - Great Grids - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int MXN = 4005;
vector<pair<int, int>> adj[MXN];
int color[MXN], bad = 0;

int dfs(int u, int c) {
    if (color[u] != -1) {
        if (color[u] != c) bad = 1;
        return 0;
    }

    color[u] = c;

    for (auto p: adj[u]) dfs(p.first, c ^ p.second);

    return 0;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;

        for (int i = 0; i < k; ++i) {
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;

            --x1, --x2, --y1, --y2;

            adj[min(x1, x2)].push_back({ n + min(y1, y2), (x1 + y1 != x2 + y2) });
            adj[n + min(y1, y2)].push_back({ min(x1, x2), (x1 + y1 != x2 + y2) });
        }

        fill(color, color+n+m, -1);
        bad = 0;

        for (int i = 0; i < n + m; ++i) {
            if (color[i] == -1) dfs(i, 0);
        }

        cout << (bad ? "NO\n" : "YES\n");

        for (int i = 0; i < n+m; ++i) adj[i].clear();
    }

    return 0;
}