Cod sursa(job #2517684)

Utilizator Alex_BubBuburuzan Alexandru Alex_Bub Data 3 ianuarie 2020 22:46:36
Problema Matrice 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

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

const int NMax = 300, MMax = 20000;

int Code[NMax + 5][NMax + 5], N, M, dl[4] = {-1, 0, 1, 0}, dc[4] = {0, 1, 0, -1};
int H[NMax * NMax + 5], TT[NMax * NMax + 5], Start[MMax + 5], Stop[MMax + 5], Sol[MMax + 5];

struct cell{int l, c, val;};
vector <cell> V;

pair<int, int> Q[MMax + 5];

int Root(int Node)
{
    while(TT[Node] != Node)
        Node = TT[Node];

    return Node;
}

void Unite(int R1, int R2)
{
    R1 = Root(R1), R2 = Root(R2);
    if(R1 == R2) return;

    if(H[R1] < H[R2]) TT[R1] = R2;
    if(H[R1] > H[R2]) TT[R2] = R1;
    if(H[R1] == H[R2]) TT[R2] = R1, H[R1]++;
}

void Add(cell Node)
{
    int l = Node.l, c = Node.c, nl, nc, Neighbor;
    TT[Code[l][c]] = Code[l][c];

    for(int t = 0; t < 4; t++)
    {
        nl = l + dl[t], nc = c + dc[t];
        Neighbor = Code[nl][nc];

        if(TT[Neighbor] && Neighbor)
            Unite(Neighbor, Code[l][c]);
    }
}

inline bool compare(cell A, cell B)
{
    return A.val < B.val;
}

int main()
{
    fin >> N >> M;

    for(int i = 1, x; i <= N; i++)
        for(int j = 1; j <= N; j++)
        {
            fin >> x;
            V.push_back({i, j, x});
            Code[i][j] = N * (i - 1) + j;
        }

    for(int i = 1, x1, x2, y1, y2; i <= M; i++)
    {
        fin >> x1 >> y1 >> x2 >> y2;
        Start[i] = Code[x1][y1], Stop[i] = Code[x2][y2];
        Q[i] = {0, i};
    }
    sort(V.begin(), V.end(), compare);
    bool changeQ = false;

    for(int step = (1 << 19); step > 0; step >>= 1)
    {
        if(changeQ == true)
            sort(Q + 1, Q + M + 1);

        int ct = V.size() - 1;
        changeQ = false;

        for(int i = 1; i <= N * N; i++)
            H[i] = 1, TT[i] = 0;

        for(int i = M; i > 0; i--)
        {
            while(ct >= 0 && V[ct].val >= Q[i].first + step)
                Add(V[ct]), ct--;

            int idx = Q[i].second;
            int R1 = Root(Start[idx]), R2 = Root(Stop[idx]);

            if(R1 && R2 && R1 == R2)
                Q[i].first += step, changeQ = true;
        }
    }
    for(int i = 1; i <= M; i++)
        Sol[Q[i].second] = Q[i].first;

    for(int i = 1; i <= M; i++)
        fout << Sol[i] << '\n';

    fin.close();
    fout.close();

    return 0;
}