Author : Dipu Kumar Mohanto CSE, Batch - 6 BRUR. Problem Statement : M - Mountaineers Source : Codeforces GYM Category : Data Structure Algorithm : Disjoint Set Union Verdict : Accepted
Tutorial : https://codeforces.com/blog/entry/75369
- #include "bits/stdc++.h"
- using namespace std;
- #define ll long long int
- #define endl '\n'
- signed main()
- {
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- #ifndef ONLINE_JUDGE
- freopen("in.txt", "r", stdin);
- #endif // ONLINE_JUDGE
- int n, m, q;
- cin >> n >> m >> q;
- vector < vector <int> > cell_node(n + 1, vector <int>(m + 1));
- vector < vector <int> > grid(n + 1, vector <int>(m + 1));
- int ptr = 0;
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- cin >> grid[i][j];
- cell_node[i][j] = ++ptr;
- }
- }
- struct Edge
- {
- int u, v, w;
- Edge(int u = 0, int v = 0, int w = 0)
- : u(u), v(v), w(w) {}
- bool operator < (const Edge &other) const
- {
- return w < other.w;
- }
- };
- int dr[4] = {+0, -1, +0, +1};
- int dc[4] = {-1, +0, +1, +0};
- function <bool(int, int)> valid = [&](int r, int c)
- {
- return r >= 1 and r <= n and c >= 1 and c <= m;
- };
- vector <Edge> edges;
- for (int i = 1; i <= n; i++)
- {
- for (int j = 1; j <= m; j++)
- {
- for (int f = 0; f < 4; f++)
- {
- int x = i + dr[f];
- int y = j + dc[f];
- if (valid(x, y))
- {
- int u = cell_node[i][j];
- int v = cell_node[x][y];
- int w = max(grid[i][j], grid[x][y]);
- edges.emplace_back(u, v, w);
- }
- }
- }
- }
- sort(edges.begin(), edges.end());
- vector <int> par(ptr + 1);
- vector <int> max_cost(ptr + 1);
- vector <int> ans(q + 1);
- set <int> st[ptr + 1];
- for (int i = 1; i <= q; i++)
- {
- int x1, y1, x2, y2;
- cin >> x1 >> y1 >> x2 >> y2;
- if (x1 == x2 and y1 == y2)
- {
- ans[i] = grid[x1][y1];
- continue;
- }
- int u = cell_node[x1][y1];
- int v = cell_node[x2][y2];
- st[u].insert(i);
- st[v].insert(i);
- }
- for (int i = 1; i <= ptr; i++) par[i] = i;
- function <int(int)> find_rep = [&](int r)
- {
- if (r == par[r]) return r;
- return par[r] = find_rep(par[r]);
- };
- for (Edge it : edges)
- {
- int u = it.u;
- int v = it.v;
- int w = it.w;
- int p = find_rep(u);
- int q = find_rep(v);
- if (p == q) continue;
- int szp = st[p].size();
- int szq = st[q].size();
- if (szp < szq)
- {
- swap(p, q);
- swap(max_cost[p], max_cost[q]);
- }
- vector <int> del;
- for (int x : st[q])
- {
- if (st[p].find(x) != st[p].end()) del.push_back(x);
- st[p].insert(x);
- }
- st[q].clear();
- par[q] = p;
- max_cost[p] = max(max_cost[p], max_cost[q]);
- max_cost[p] = max(w, max_cost[p]);
- for (int d : del)
- {
- st[p].erase(d);
- ans[d] = max_cost[p];
- }
- }
- for (int i = 1; i <= q; i++) cout << ans[i] << endl;
- }
