Cod sursa(job #2920282)

Utilizator nhphucqtNguyen Hoang Phuc nhphucqt Data 23 august 2022 14:14:10
Problema Matrice 2 Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 5.75 kb
// Dungeon

/* Gợi ý giới hạn
1 <= a[i][j] <= 1e6
Sub1: n <= 50, q <= 10
Sub2: n <= 100, q <= 100 (có thể bỏ)
Sub3: n <= 200, q <= 1000
Sub4: n <= 300, q <= 1e5
Sub5: n <= 500, q <= 1e6
*/

// nhánh cận các thứ, cố gắng code các sub tối ưu nhất có thể (tránh code sub nhỏ ăn sub lớn)
// bò: dfs giới hạn lần chạy (vd: 100 lần) nếu chưa đến đích out ra false (có thể sai)
// bò: ngắt dijkstra nếu gặp đích (có thể sai)
// thử code cách cnp song song sử dụng dfs/bfs thay dsu (tle)

#include <bits/stdc++.h>

using namespace std;

struct Query {
    int x, y, u, v, id;
};

const int D[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
const int N = 507;
const int Q = 1e6+7;
int n, q, a[N][N];
Query ques[Q];

bool inside(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

namespace sub1 {
    int dist[N][N];
    int dijkstra(int su, int sv, int tu, int tv) {
        priority_queue<pair<int, pair<int,int>>> heap;
        memset(dist, 0, sizeof dist);
        dist[su][sv] = a[su][sv];
        heap.emplace(dist[su][sv], make_pair(su,sv));
        while (!heap.empty()) {
            int u = heap.top().second.first;
            int v = heap.top().second.second;
            int w = heap.top().first;
            heap.pop();
            if (w != dist[u][v]) continue;
            // if (u == tu && v == tv) 
            //     return dist[u][v];
            for (int i = 0; i < 4; ++i) {
                int x = u + D[i][0];
                int y = v + D[i][1];
                if (inside(x,y)) {
                    if (dist[x][y] < min(dist[u][v], a[x][y])) {
                        dist[x][y] = min(dist[u][v], a[x][y]);
                        heap.emplace(dist[x][y], make_pair(x,y));
                    }
                }
            }
        }
        return dist[tu][tv];
    }
    void solve() {
        for (int i = 1; i <= q; ++i) {
            cout << dijkstra(ques[i].x, ques[i].y, ques[i].u, ques[i].v) << '\n';
        }
    }
}

namespace sub2 {
    bool mark[N][N];
    bool bfs(int su, int sv, int tu, int tv, int k) {
        queue<pair<int,int>> q;
        memset(mark, false, sizeof mark); // giam ve n
        mark[su][sv] = true;
        q.emplace(su, sv);
        while (!q.empty()) {
            int u = q.front().first;
            int v = q.front().second;
            q.pop();
            if (u == tu && v == tv) 
                return true;
            for (int i = 0; i < 4; ++i) {
                int x = u + D[i][0];
                int y = v + D[i][1];
                if (inside(x,y) && a[x][y] >= k && !mark[x][y]) {
                    mark[x][y] = true;
                    q.emplace(x,y);
                }
            }
        }
        return false;
    }
    void solve() {
        for (int i = 1; i <= q; ++i) {
            int l = 1;
            int r = min(a[ques[i].x][ques[i].y], a[ques[i].u][ques[i].v]);
            while (l < r) {
                int m = l+r+1>>1;
                if (bfs(ques[i].x,ques[i].y,ques[i].u,ques[i].v, m))
                    l = m;
                else r = m-1;
            }
            cout << l << '\n';
        }
    }
}

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

const int NODE = N*N;
const int EDGE = NODE*2;
struct Edge {
    int x, y, w;
    Edge() {}
    Edge(int _x, int _y, int _w) {
        x = _x; y = _y; w = _w;
    }
};

struct Event {
    int u, v, f_u, f_v;
    Event() {}
    Event(int _u, int _v, int _fu, int _fv) {
        u = _u; v = _v; f_u = _fu; f_v = _fv;
    }
} events[EDGE];

int numNode, numEdge, numEvent;
pair<int,int> newQues[Q];
Edge edges[EDGE];
int fa[NODE];
int ans[Q];

int root(int x) {
    return fa[x] < 0 ? x : root(fa[x]);
}

void Unite(int u, int v) {
    u = root(u);
    v = root(v);
    events[numEvent++] = Event(u, v, fa[u], fa[v]);
    if (u == v) {
        return;
    }
    if (fa[u] > fa[v]) swap(u,v);
    fa[u] += fa[v];
    fa[v] = u;
}

void rollback() {
    numEvent--;
    fa[events[numEvent].u] = events[numEvent].f_u;
    fa[events[numEvent].v] = events[numEvent].f_v;
}

void parallel(int l, int r, vector<int> &v) {
    if (l == r) {
        for (int i : v) ans[i] = edges[l].w;
        return;
    }
    int m = l+r>>1;
    for (int i = l; i <= m; ++i)
        Unite(edges[i].x,edges[i].y);
    vector<int> lef, rig;
    for (int i : v) {
        if (root(newQues[i].first) == root(newQues[i].second)) {
            lef.push_back(i);
        }
        else {
            rig.push_back(i);
        }
    }
    parallel(m+1, r, rig);
    for (int i = l; i <= m; ++i)
        rollback();
    rig = vector<int>();
    parallel(l, m, lef);
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    freopen("matrice2.in", "r", stdin);
    freopen("matrice2.out", "w", stdout);

    cin >> n >> q;
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
        cin >> a[i][j];
    }
    for (int i = 1; i <= q; ++i) {
        cin >> ques[i].x >> ques[i].y >> ques[i].u >> ques[i].v;
        ques[i].id = i;
    }

    for (int i = 1; i <= q; ++i) {
        newQues[i].first = getId(ques[i].x,ques[i].y);
        newQues[i].second = getId(ques[i].u,ques[i].v);
    }
    numNode = n * n;
    numEdge = 0;
    for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) {
        if (i < n)
            edges[numEdge++] = Edge(getId(i,j), getId(i+1,j), min(a[i][j],a[i+1][j]));
        if (j < n)
            edges[numEdge++] = Edge(getId(i,j), getId(i,j+1), min(a[i][j],a[i][j+1]));
    }
    sort(edges,edges+numEdge,[&](const Edge &a, const Edge &b) {
        return a.w > b.w;
    });
    vector<int> v;
    for (int i = 1; i <= q; ++i) 
        v.push_back(i);
    memset(fa, -1, (numNode+1) * sizeof(int));
    parallel(0, numEdge-1, v);
    for (int i = 1; i <= q; ++i)
        cout << ans[i] << '\n';

    return 0;
}