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.
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]; vector<ii> adj[100001]; void dfs(int u, int p) { for (int i = 0; i < adj[u].size(); i++) { int v = adj[u][i].first, val = adj[u][i].second; 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); adj[u].push_back(ii(v, val)); adj[v].push_back(ii(u, val)); } } 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'; } }
Comments