Cod sursa(job #2349407)

Utilizator Alexa2001Alexa Tudose Alexa2001 Data 20 februarie 2019 14:15:28
Problema Matrice 2 Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax = 303, Qmax = 20005, lim = 1e6;

int n, q;
int a[Nmax*Nmax], ans[Qmax];

vector< pair<int,int> > mom, vals;
pair<int,int> b[Qmax];


int cell(int x, int y) { return (x-1) * n + y; }

namespace forest
{
    static int t[Nmax * Nmax];

    int boss(int x)
    {
        if(x == t[x]) return x;
        return t[x] = boss(t[x]);
    }

    bool connected(int x, int y)
    {
        return boss(x) == boss(y);
    }

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

    void unite(int x, int y)
    {
        x = boss(x); y = boss(y);
        t[x] = y;
    }

    void baga(int x)
    {
        if(x > n && a[x - n] >= a[x]) unite(x-n, x);
        if(a[x - 1] >= a[x]) unite(x-1, x);
        if(a[x + n] >= a[x]) unite(x+n, x);
        if(a[x + 1] >= a[x]) unite(x+1, x);
    }
};

void check(int add)
{
    int i = 0;
    sort(mom.begin(), mom.end());
    reverse(mom.begin(), mom.end());

    forest :: reset();

    for(auto &it : mom)
    {
        while(i < vals.size() && vals[i].first >= it.first + add)
            forest :: baga(vals[i++].second);

        if(forest :: connected(b[it.second].first, b[it.second].second))
            it.first += add;
    }
}

int main()
{
    int i, j, x, X1, Y1, X2, Y2;

    fin >> n >> q;
    for(i=1; i<=n; ++i)
        for(j=1; j<=n; ++j)
        {
            fin >> x; a[cell(i,j)] = x; assert(x > 0);
            vals.push_back({ x, cell(i, j) });
        }
    sort(vals.begin(), vals.end());
    reverse(vals.begin(), vals.end());

    for(i=1; i<=q; ++i)
    {
        fin >> X1 >> Y1 >> X2 >> Y2;
        b[i] = {cell(X1, Y1), cell(X2, Y2)};
        mom.push_back({0, i});
    }

    for(i=20; i>=0; --i) check(1<<i);

    for(auto it : mom) ans[it.second] = it.first;
    for(i=1; i<=q; ++i) fout << ans[i] << '\n';

    return 0;
}