Editorial for Bedao Grand Contest 09 - QPATH

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Code mẫu

#include <bits/stdc++.h>

using namespace std;
const string filename = "QPATH";

typedef pair<int, int> ii;
typedef pair<int, ii> iii;

int n, m;
vector< vector<int> > a;
int q;
int x1, y1, x2, y2;

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0 , -1};

int par[100001];

int anc(int x)
{
if (par[x] == x) return x;
return par[x] = anc(par[x]);
}

void join(int x, int y)
{
par[anc(x)] = anc(y);
}

int id(int row, int col)
{
return (row - 1) * m + col;
}

int h[100001];
int mn_val[100001][21], pt[100001][21];

void dfs(int u, int p)
{
for (int i = 0; i < adj[u].size(); i++) {
if (v == p) continue;
h[v] = h[u] + 1;
dfs(v, u);
mn_val[v][0] = val;
pt[v][0] = u;
}
}

int cal(int u, int v)
{
if (h[u] > h[v])
swap(u, v);
int ans = 1e9;
for (int j = 20; j >= 0; j--)
if (h[pt[v][j]] >= h[u]) {
ans = min(ans, mn_val[v][j]);
v = pt[v][j];
}
if (u == v)
return ans;
for (int j = 20; j >= 0; j--)
if (pt[u][j] != pt[v][j]) {
ans = min(ans, mn_val[u][j]);
ans = min(ans, mn_val[v][j]);
u = pt[u][j];
v = pt[v][j];
}
ans = min(ans, mn_val[u][0]);
ans = min(ans, mn_val[v][0]);
return ans;
}

int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

freopen( (filename + ".inp").c_str(), "r", stdin);
freopen( (filename + ".out").c_str(), "w", stdout);

cin >> n >> m;
a.resize(n + 1);
for (int i = 1; i <= n; i++) {
a[i].resize(m + 1);
for (int j = 1; j <= m; j++)
cin >> a[i][j];
}

vector<iii> E;
for (int x = 1; x <= n; x++)
for (int y = 1; y <= m; y++)
for (int k = 0; k < 4; k++) {
int xx = x + dx[k];
int yy = y + dy[k];
if (1 <= xx && xx <= n && 1 <= yy && yy <= m) {
E.push_back(iii(min(a[x][y], a[xx][yy]), ii(id(x, y), id(xx, yy))));
}
}

sort (E.begin(), E.end(), greater<iii>());
for (int i = 1; i <= n * m; i++)
par[i] = i;
for (int i = 0; i < E.size(); i++) {
int val = E[i].first, u = E[i].second.first, v = E[i].second.second;
if (anc(u) != anc(v)) {
join(u, v);
}
}

h[1] = 1;
dfs(1, -1);
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= n * m; i++) {
pt[i][j] = pt[pt[i][j - 1]][j - 1];
mn_val[i][j] = min(mn_val[i][j - 1], mn_val[pt[i][j - 1]][j - 1]);
}

cin >> q;
while (q--) {
cin >> x1 >> y1 >> x2 >> y2;
cout << cal(id(x1, y1), id(x2, y2)) << '\n';
}
}