Submission #63068220

---

Source Code Expand

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cassert>
using namespace std;

int root[250000];
int compute_root(int a)
{
    return a == root[a] ? a : root[a] = compute_root(root[a]);
}
int unite(int a, int b)
{
    a = compute_root(a);
    b = compute_root(b);
    if (a == b)
        return 0;
    if (rand() % 2)
    {
        swap(a, b);
    }
    root[a] = b;
    return 1;
}

int h, w;
int C(int r, int c)
{
    return r * w + c;
}

vector<tuple<int, int, int>> es;
int F[500][500];

vector<pair<int, int>> g[250000];
int parent[18][250000];
int cost[18][250000];
int depth[250000];
void dfs(int r, int p, int pc,int d)
{
    parent[0][r] = p;
    cost[0][r] = pc;
    depth[r] = d;
    for (auto [i, w] : g[r])
    {
        if (i == p)
        {
            continue;
        }
        dfs(i, r, w, d+1);
    }
}

int query(int a,int b){
    assert(a != b);

    if( depth[a] > depth[b])  swap(a, b);
    int d = depth[b] - depth[a];

    int cst = 1145141919;
    for(int i = 0 ; i < 18 ; i++){
        if( d >> i & 1 ){
            cst = min(cst, cost[i][b]);
            b = parent[i][b];
        }
    }

    for(int i = 17 ; i >= 0 ; i--){
        if( parent[i][a] != parent[i][b]){
            cst = min(cst, cost[i][a]);
            cst = min(cst, cost[i][b]);
            a = parent[i][a];
            b = parent[i][b];
        }
    }
    if( a == b ){
        return cst;
    }
    cst = min(cst, cost[0][a]);
    cst = min(cst, cost[0][b]);
    a = parent[0][a];
    b = parent[0][b];
    assert(a==b);
    return cst;
}

int main()
{

    cin >> h >> w;
    int n = h * w;
    for (int i = 0; i < n; i++)
        root[i] = i;
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> F[i][j];
        }
    }
    for (int i = 0; i + 1 < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            int c = min(F[i][j], F[i + 1][j]);
            es.push_back({c, C(i, j), C(i + 1, j)});
        }
    }
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j + 1 < w; j++)
        {
            int c = min(F[i][j], F[i][j + 1]);
            es.push_back({c, C(i, j), C(i, j + 1)});
        }
    }
    sort(es.rbegin(), es.rend());
    for (auto [we, i, j] : es)
    {
        if (unite(i, j))
        {
            g[i].push_back({j, we});
            g[j].push_back({i, we});
            
        }
    }
    memset(parent, -1, sizeof(parent));
    dfs(0, -1, 0, 0);
    for (int b = 0; b + 1 < 18; b++)
    {
        for (int i = 0; i < n; i++)
        {
            if (parent[b][i] != -1)
            {
                int np = parent[b][parent[b][i]];
                parent[b + 1][i] = np;
                cost[b + 1][i] = min(cost[b][parent[b][i]], cost[b][i]);
            }
        }
    }
    int Q;
    cin >> Q;
    for(int i = 0 ; i < Q ; i++){
        int a, b, y, c, d, z;
        cin >> a >> b >> y >> c >> d >> z;
        --a, --b;
        --c, --d;
        int A = C(a, b);
        int B = C(c, d);
        if( A == B ){
            cout << abs(y-z) << endl;
        }else{
            int m = query(A, B);
            if( m >= y && m >= z ){
                cout << abs(y-z) << endl;
            }else{
                cout << abs(y - m) + abs(z - m) << endl;
            }
            
        }
        
    }

}

Submission Info

Judge Result