Cod sursa(job #2460362)

Utilizator StanCatalinStanCatalin StanCatalin Data 23 septembrie 2019 15:36:22
Problema Matrice 2 Scor 95
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream in("matrice2.in");
ofstream out("matrice2.out");

const int dirx[4] = {-1, 0, 1, 0};
const int diry[4] = {0, 1, 0, -1};


const int dim = 305;
const int Q = 20005;

int n,m,mat[dim][dim],sol[Q],que[Q],pus[dim][dim],POZ[Q],PARENT[dim*dim];
int x[dim*dim],y[dim*dim],poz[dim*dim],a[dim*dim];
int x1[Q],y1[Q],x2[Q],y2[Q];

bool cmp(int x,int y)
{
    return (a[x] > a[y]);
}

bool cmp2(int x,int y)
{
    return (que[x] > que[y]);
}

int Find(int x)
{
    if (x != PARENT[x])
    {
        PARENT[x] = Find(PARENT[x]);
    }
    return PARENT[x];
}

int main()
{
    int cx,cy,j,k,i;
    int cnt = 0;
    in >> n >> m;
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<=n; j++)
        {
            cnt++;
            mat[i][j] = cnt;
            x[cnt] = i;
            y[cnt] = j;
            in >> a[cnt];
            poz[cnt] = cnt;
        }
    }
    for (int i=1; i<=m; i++)
    {
        in >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    }
    sort(poz+1,poz+n*n+1,cmp);
    int step = 1;
    while (step < a[poz[1]])
    {
        step *= 2;
    }
    for (;step ; step >>= 1)
    {
        for (int i=1; i<=m; i++)
        {
            que[i] = sol[i] + step;
            POZ[i] = i;
        }

        for (int i=1; i<=n; i++)
        {
            for (int j=1; j<=n; j++)
            {
                pus[i][j] = 0;
            }
        }

        sort(POZ+1,POZ+m+1,cmp2);

        for (int i=1; i<=n*n; i++)
        {
            PARENT[i] = i;
        }

        for (i=1,j=1; i<=n*n;)
        {
            for (k=j; j<=m && que[POZ[j]] > a[poz[i]]; j++)
            {
                if (Find(mat[x1[POZ[j]]][y1[POZ[j]]]) == Find(mat[x2[POZ[j]]][y2[POZ[j]]]))
                {
                    sol[POZ[j]] += step;
                }
            }

            for (k=i; i<=n*n && a[poz[i]] == a[poz[k]]; i++)
            {
                pus[x[poz[i]]][y[poz[i]]] = 1;

                for (int p=0; p<4; p++)
                {
                    cx = x[poz[i]] + dirx[p];
                    cy = y[poz[i]] + diry[p];

                    if (cx > 0 && cx <= n && cy >= 0 && cy <= n && pus[cx][cy])
                    {
                        PARENT[PARENT[Find(mat[cx][cy])]] = PARENT[poz[i]];
                    }
                }
            }
        }

        for (j; j<=m; j++)
        {
            if (Find(mat[x1[POZ[j]]][y1[POZ[j]]]) == Find(mat[x2[POZ[j]]][y2[POZ[j]]]))
            {
                sol[POZ[j]] += step;
            }
        }

    }

    for (int i=1; i<=m; i++)
    {
        out << sol[i] << "\n";
    }
    return 0;
}