Cod sursă (job #819664)

#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
ifstream fin ("virus2.in");
ofstream fout ("virus2.out");
int find(vector<int>& parent, int nod) {
    if (parent[nod] != nod) {
        parent[nod] = find(parent, parent[nod]);
    }
    return parent[nod];
}
void unite(int a, int b, vector<int>& parent, vector<int>& rank) {
    a = find(parent, a);
    b = find(parent, b);
    if (a == b) {
        return;
    }
    if (rank[a] < rank[b]) {
        swap(a, b);
    }
    parent[b] = a;
    if (rank[a] == rank[b]) {
        rank[a]++;
    }
}
struct query {
    int cer, L1, C1, L2, C2;
    int cnt;
};
void fill(int i, int j, int n, vector<vector<int>> &mat, vector<int> &parent, vector<int> &rank) {
    if (mat[i][j] == 0) {
        mat[i][j] = 1;
        int idx = i * n + j;
        if (i > 0 && mat[i - 1][j] == 1)
            unite(idx, (i - 1) * n + j, parent, rank);
        if (i + 1 < n && mat[i + 1][j] == 1)
            unite(idx, (i + 1) * n + j, parent, rank);
        if (j > 0 && mat[i][j - 1] == 1)
            unite(idx, i * n + j - 1, parent, rank);
        if (j + 1 < n && mat[i][j + 1] == 1)
            unite(idx, i * n + j + 1, parent, rank);
    }
}
void reactiv(int L1, int C1, int L2, int C2, int n, vector<vector<int>> &mat, vector<int> &parent, vector<int> &rank) {
    for (int col = C1; col <= C2; col++) {
        fill(L1, col, n, mat, parent, rank);
        fill(L2, col, n, mat, parent, rank);
    }
    for (int lin = L1; lin <= L2; lin++) {
        fill(lin, C1, n, mat, parent, rank);
        fill(lin, C2, n, mat, parent, rank);
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    fin >> n >> m;
    vector<query> v(m);
    int cntq = 0;
    for (int i = 0; i < m; i++) {
        fin >> v[i].cer >> v[i].L1 >> v[i].C1 >> v[i].L2 >> v[i].C2;
        if (v[i].cer == 2) {
            cntq++;
            v[i].cnt = cntq;
        } else {
            v[i].cnt = -1;
        }
    }
    vector<vector<int>> mat(n, vector<int>(n, 1));
    for (const auto &q : v) {
        if (q.cer == 1) {
            int L1 = q.L1 - 1, C1 = q.C1 - 1, L2 = q.L2 - 1, C2 = q.C2 - 1;
            for (int l = L1; l <= L2; l++) {
                mat[l][C1] = 0;
                mat[l][C2] = 0;
            }
            for (int c = C1; c <= C2; c++) {
                mat[L1][c] = 0;
                mat[L2][c] = 0;
            }
        }
    }
    vector<int> parent(n * n);
    vector<int> rank(n * n, 0);
    for (int i = 0; i < n * n; i++)
        parent[i] = i;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (mat[i][j] == 1) {
                int idx = i * n + j;
                if (j + 1 < n && mat[i][j + 1] == 1)
                    unite(idx, i * n + (j + 1), parent, rank);
                if (i + 1 < n && mat[i + 1][j] == 1)
                    unite(idx, (i + 1) * n + j, parent, rank);
            }
        }
    }
    vector<string> sol(cntq);
    for (int i = m - 1; i >= 0; i--) {
        if (v[i].cer == 2) {
            int l1 = v[i].L1 - 1;
            int c1 = v[i].C1 - 1;
            int l2 = v[i].L2 - 1;
            int c2 = v[i].C2 - 1;
            int idx1 = l1 * n + c1;
            int idx2 = l2 * n + c2;
            if (mat[l1][c1] == 1 && mat[l2][c2] == 1 && find(parent, idx1) == find(parent, idx2)) {
                sol[v[i].cnt-1]="DA";
            } else {
                sol[v[i].cnt-1]="NU";
            }
        } else {
            int L1 = v[i].L1 - 1;
            int C1 = v[i].C1 - 1;
            int L2 = v[i].L2 - 1;
            int C2 = v[i].C2 - 1;
            reactiv(L1, C1, L2, C2, n, mat, parent, rank);
        }
    }
    for (int i=0; i < cntq; i++)
        {fout << sol[i] << "\n";}

    return 0;
}