Cod sursă (job #784288)

#include <bits/stdc++.h>
using namespace std;
#define NMAX 2000
#define QMAX 100000
struct squery {
    int tip;
    int l1, l2, c1, c2;
    char ans;
};
squery query[QMAX+1];

int n;
int comp = 1;
int mat[NMAX+2][NMAX+2];

void bord( int l1, int l2, int c1, int c2 ) {
    int i;
    for( i = l1; i <= l2; i++ )
        mat[i][c1] = mat[i][c2] = comp;
    for( i = c1; i <= c2; i++ )
        mat[l1][i] = mat[l2][i] = comp;
    comp++;
}

int t[NMAX*NMAX+1];
int find1( int x ) {
    if( x == t[x] )
        return x;
    return t[x] = find1(t[x]);
}

void union1( int a, int b ) {
    int x = find1( a );
    int y = find1( b );
    if( x != y )
        t[x] = y;
}

int dlin[4] = { -1, 1, 0, 0 };
int dcol[4] = { 0, 0, -1, 1 };

void fill1( int lin, int col, int nr ) {
    queue<pair<int, int>> q;
    q.push( { lin, col } );
    mat[lin][col] = nr;
    while( !q.empty() ) {
        int lin = q.front().first;
        int col = q.front().second;
        q.pop();
        for( int k = 0; k < 4; k++ ) {
            if( lin + dlin[k] >= 1 && lin + dlin[k] <= n && col + dcol[k] >= 1 && col + dcol[k] <= n && !mat[lin+dlin[k]][col+dcol[k]] ) {
                mat[lin+dlin[k]][col+dcol[k]] = nr;
                q.push({ lin + dlin[k], col + dcol[k] });
            }
        }
    }
}

void desinfect( int lin, int col ) {
    int k;
    for( k = 0; k < 4; k++ ) {
        if( mat[lin][col] < mat[lin+dlin[k]][col+dcol[k]] )
            union1( mat[lin][col], mat[lin+dlin[k]][col+dcol[k]] );
    }
}

int main() {
    int q, i, j, last;
    FILE *fin,*fout;
    fin=fopen("virus2.in","r");
    fscanf(fin,"%d%d",&n,&q);
    for( i = 0; i < q; i++ ) {
        fscanf(fin,"%d%d%d%d%d",&query[i].tip,&query[i].l1,&query[i].c1,&query[i].l2,&query[i].c2);
        if(query[i].tip==1)
            bord(query[i].l1,query[i].l2,query[i].c1,query[i].c2);
    }
    last=comp-1;
    for( i = 1; i <= n; i++ ) {
        for( j = 1; j <= n; j++ ) {
            if( !mat[i][j] ) {
                fill1( i, j, comp );
                comp++;
            }
        }
    }
    for(i=1; i<=n*n; i++)
        t[i]=i;
    for(i=q-1; i>=0; i--) {
        if( query[i].tip == 2 ) {
            if( mat[query[i].l1][query[i].c1] > last && mat[query[i].l2][query[i].c2]>last) {
                int x = find1( mat[query[i].l1][query[i].c1] );
                int y = find1( mat[query[i].l2][query[i].c2] );
                if(x==y) {
                    query[i].ans=1;
                } else {
                    query[i].ans =0;
                }
            } else
                query[i].ans=0;
        } else {
            last--;
            for( j = query[i].l1; j <= query[i].l2; j++ ) {
                desinfect( j, query[i].c1 );
                desinfect( j, query[i].c2 );
            }
            for( j = query[i].c1; j <= query[i].c2; j++ ) {
                desinfect( query[i].l1, j );
                desinfect( query[i].l2, j );
            }
        }
    }
    fout=fopen("virus2.out","w");
    for( i = 0; i < q; i++ ) {
        if( query[i].tip == 2 ) {
            if(query[i].ans==1) {
                fprintf(fout,"DA\n");
            } else {
                fprintf(fout,"NU\n");
            }
        }
    }
    fclose(fin);
    fclose(fout);
    return 0;
}