Cod sursă (job #732044)

#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream cin ("virus2.in");
ofstream cout ("virus2.out");

const int M = 1e5
const int N = 2002;

vector <int> rez;

int tata[N * N + 2], h[N * N + 2];

bool viz[N + 1][N + 1], viz1[N + 1][N + 1];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

struct ceva
{
    int cer, l1, l2, c1, c2;
} a[M + 1];

int n, q;

namespace DSU
{
int create_key (int x, int y)
{
    return (x - 1) * n + y;
}
int rad (int node)
{
    if (tata[node] == node)return node;
    return tata[node] = rad(tata[node]);
}
void unite (int rx, int ry)
{
    if (rx != ry)
    {
        if (h[rx] < h[ry])
        {
            tata[rx] = ry;
            h[ry] += h[rx];
        }
        else
        {
            tata[ry] = rx;
            h[rx] += h[ry];
        }
    }
}



void combine (int x, int y, int xx, int yy)
{
    int node1 = create_key(x, y);
    int node2 = create_key(xx, yy);
    int rx = rad(node1);
    int ry = rad (node2);
    unite(rx, ry);
}
}

bool inside (int x, int y)
{
    return (x >= 1 && y >= 1 && x <= n && y <= n);
}

void dfs (int x, int y)
{
    viz[x][y] = 1;
    for (int i = 0; i < 4; ++i)
    {
        int xx = x + dx[i];
        int yy = y + dy[i];
        if (inside (xx, yy) && (!viz[xx][yy]) && (!viz1[xx][yy]))
            DSU::combine(x, y, xx, yy), dfs (xx, yy);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= q; ++i)
    {
        cin >> a[i].cer >> a[i].l1 >> a[i].c1 >> a[i].l2 >> a[i].c2;
        if (a[i].cer == 1)
        {
            for (int l = a[i].l1; l <= a[i].l2; ++l)
                viz1[l][a[i].c1] = viz1[l][a[i].c2] = 1;
            for (int l = a[i].c1; l <= a[i].c2; ++l)
                viz1[a[i].l1][l] = viz1[a[i].l2][l] = 1;
        }
    }
    for (int i = 1; i <= n * n; ++i)
        tata[i] = i, h[i] = 1;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (!viz[i][j] && !viz1[i][j])
                dfs (i, j);
    for (int i = q; i >= 1; --i)
    {
        if (a[i].cer == 2)
        {
            int node1 = DSU::create_key(a[i].l1, a[i].c1);
            int node2 = DSU::create_key(a[i].l2, a[i].c2);
            rez.push_back ((bool)(DSU::rad(node1) == DSU::rad(node2)));
        }
        else
        {
            for (int l = a[i].l1; l <= a[i].l2; ++l)
                viz1[l][a[i].c1] = viz1[l][a[i].c2] = 1;
            for (int l = a[i].c1; l <= a[i].c2; ++l)
                viz1[a[i].l1][l] = viz1[a[i].l2][l] = 1;
            for (int l = a[i].l1; l <= a[i].l2; ++l)
                for (int j = 0; j < 4; ++j)
                {
                    int x = l + dx[j];
                    int y1 = a[i].c1 + dy[j];
                    int y2 = a[i].c2 + dy[j];
                    if (!viz1[x][y1] && inside (x, y1))DSU::combine(l, a[i].c1, x, y1);
                    if (!viz1[x][y1] && inside (x, y2))DSU::combine(l, a[i].c2, x, y2);
                }

            for (int l = a[i].c1; l <= a[i].c2; ++l)
                for (int j = 0; j < 4; ++j)
                {
                    int y = l + dy[j];
                    int x1 = a[i].l1 + dx[j];
                    int x2 = a[i].l2 + dx[j];
                    if (!viz1[x1][y] && inside (x1, y))DSU::combine(a[i].l1, l, x1, y);
                    if (!viz1[x2][y] && inside (x2, y))DSU::combine(a[i].l2, l, x2, y);
                }
        }
    }
    reverse (rez.begin(), rez.end());
    for (auto it : rez)
        (it) ? cout << "DA\n" : cout << "NU\n";
    return 0;
}