Cod sursa(job #2676703)

Utilizator bogdi1bogdan bancuta bogdi1 Data 24 noiembrie 2020 19:39:51
Problema Matrice 2 Scor 100
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <cstdio>
#include <algorithm>
using namespace std;
struct Celule
{
    int val,x,y;
} v[90005];
bool viz[305][305];
int t[90005];
int h[90005];
struct Solutie
{
    int val,ind;
} res[90005];
int dirl[]={-1, 0, 1, 0};
int dirc[]={0, 1, 0, -1};
struct Queriuri
{
    int x1,y1,x2,y2;
} query[20005];
bool cmp(Celule &a, Celule &b)
{
    return a.val>b.val;
}
bool cmp1(Solutie &a, Solutie &b)
{
    return a.val<b.val;
}
bool cmp2(Solutie &a, Solutie &b)
{
    return a.ind<b.ind;
}
int FindSet(int x)
{
    while(x!=t[x])
        x=t[x];
    return x;
}
bool UnionSet(int x, int y)
{
    int tx,ty;
    tx=FindSet(x);
    ty=FindSet(y);
    if(tx==ty)
        return 0;
    else{
        if(h[tx]==h[ty]){
            h[tx]++;
            t[ty]=tx;
        }
        else{
            if(h[tx]<h[ty])
                t[tx]=ty;
            else
                t[ty]=tx;
        }
        return 1;
    }
}
int main()
{   freopen("matrice2.in", "r", stdin);
    freopen("matrice2.out", "w", stdout);
    int n,q,i,j,x,step,l;
    scanf("%d%d", &n, &q);
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++){
            scanf("%d", &x);
            v[(i-1)*n+j].val=x;
            v[(i-1)*n+j].x=i;
            v[(i-1)*n+j].y=j;
        }
    for(i=1; i<=q; i++){
        scanf("%d%d%d%d", &query[i].x1, &query[i].y1, &query[i].x2, &query[i].y2);
        res[i].ind=i;
    }
    sort(v+1, v+n*n+1, cmp);
    for(step=(1<<20); step; step>>=1){
        sort(res+1, res+q+1, cmp1);
        for(i=1; i<=n*n; i++){
            h[i]=1;
            t[i]=i;
        }
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                viz[i][j]=0;
        j=1;
        for(i=q; i>=1; i--){
            while(j<=n*n && v[j].val>=res[i].val+step){
                for(l=0; l<=3; l++)
                    if(viz[v[j].x+dirl[l]][v[j].y+dirc[l]]==1)
                        UnionSet((v[j].x+dirl[l]-1)*n+v[j].y+dirc[l], (v[j].x-1)*n+v[j].y);
                viz[v[j].x][v[j].y]=1;
                j++;
            }
            if(FindSet((query[res[i].ind].x1-1)*n+query[res[i].ind].y1)==FindSet((query[res[i].ind].x2-1)*n+query[res[i].ind].y2))
                res[i].val+=step;
        }
    }
    sort(res+1, res+q+1, cmp2);
    for(i=1; i<=q; i++)
        printf("%d\n", res[i].val);
    return 0;
}