fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define fi first
  5. #define se second
  6. #define MAX 250250
  7. #define pb push_back
  8. #define LOG 22
  9. #define inf 1000000000
  10.  
  11. struct node
  12. {
  13.     int u;
  14.     int v;
  15.     int val;
  16.     node(int _u, int _v, int _val)
  17.     {
  18.         u = _u;
  19.         v = _v;
  20.         val = _val;
  21.     }
  22.  
  23.     bool operator > (const node& other) const{
  24.         return this->val > other.val;
  25.     }
  26. };
  27.  
  28. int n,q, root;
  29. int a[MAX], parent[MAX], w[MAX], head[MAX], pos[MAX], treesize[MAX], depth[MAX], nodee[MAX];
  30. int cnt = 0;
  31. vector<node> canh;
  32. vector<int> adj[MAX];
  33.  
  34. int f[MAX][22];
  35.  
  36. inline int get(int i, int j)
  37. {
  38.     return (i-1)*n + j;
  39. }
  40.  
  41. void nhap()
  42. {
  43.     canh.reserve(MAX);
  44.     cin >> n >> q;
  45.     for(int i = 1; i<=n; i++){
  46.         for(int j = 1; j<=n; j++) cin >> a[get(i,j)];
  47.     }
  48.     for(int i = 1; i<=n; i++){
  49.         for(int j = 1; j<=n; j++){
  50.             if(i + 1 <=n) canh.pb(node(get(i,j), get(i+1,j), min(a[get(i+1, j)], a[get(i,j)])));
  51.             if(j + 1 <=n) canh.pb(node(get(i,j), get(i,j+1), min(a[get(i, j+1)], a[get(i,j)])));
  52.         }
  53.     }
  54.     sort(canh.begin(), canh.end(), greater<node>());
  55. }
  56.  
  57. int findd(int u)
  58. {
  59.     if(u == parent[u]) return u;
  60.     return parent[u] = findd(parent[u]);
  61. }
  62.  
  63. bool unionn(int u, int v)
  64. {
  65.     u = findd(u);
  66.     v = findd(v);
  67.     if(u == v) return false;
  68.     if(treesize[u] > treesize[v]){
  69.         parent[v] = u;
  70.     }else{
  71.         parent[u] = v;
  72.     }
  73.     return true;
  74. }
  75.  
  76. void make_tree()
  77. {
  78.     for(int i = 1; i<=n; i++){
  79.         for(int j = 1; j<=n; j++){ parent[get(i,j)] = get(i,j); treesize[get(i,j)] = 1;}
  80.     }
  81.     int m = canh.size();
  82.     for(int i = 0; i<m; i++){
  83.         int _u = canh[i].u;
  84.         int _v = canh[i].v;
  85.         if(unionn(_u, _v)){
  86.             adj[_u].pb(_v);
  87.             adj[_v].pb(_u);
  88.             w[_u] = a[_u];
  89.             w[_v] = a[_v];
  90.             root = _u;
  91.         }
  92.     }
  93.     depth[root] = 0;
  94.     parent[root] = 0;
  95. }
  96.  
  97. void dfs(int v, int par)
  98. {
  99.     treesize[v] = 1;
  100.     int index = -1;
  101.     int ans_index = -1;
  102.     for(int u : adj[v]){
  103.         ++index;
  104.         if(u == par) continue;
  105.         parent[u] = v;
  106.         depth[u] = depth[v] + 1;
  107.         dfs(u,v);
  108.         treesize[v] += treesize[u];
  109.         if(ans_index == -1 || treesize[u] > treesize[adj[v][ans_index]]) ans_index = index;
  110.     }
  111.     if(ans_index != 0 && ans_index != -1) swap(adj[v][0], adj[v][ans_index]);
  112. }
  113.  
  114. void decompose(int v, int par, int h)
  115. {
  116.     head[v] = h;
  117.     pos[v] = ++cnt;
  118.     nodee[cnt] = v;
  119.     for(int u : adj[v]){
  120.         if(u == par) continue;
  121.         if(u == adj[v][0]){
  122.             decompose(u,v,h);
  123.         }else{
  124.             decompose(u,v,u);
  125.         }
  126.     }
  127. }
  128.  
  129. int gett(int l, int r)
  130. {
  131.     int k = 31 - __builtin_clz(r-l+1);
  132.     return min(f[l][k], f[r - (1<<k) + 1][k]);
  133. }
  134.  
  135. void process()
  136. {
  137.     vector<int> a(MAX+1);
  138.     for(int i = 1; i<=cnt; i++) a[i] = w[nodee[i]];
  139.     for(int i = 1; i<= cnt; i++) f[i][0] = a[i];
  140.     for(int j = 1; (1<<j) <= cnt; j++){
  141.         for(int i = 1; i + (1<<j) - 1 <= cnt; i++) f[i][j] = min(f[i][j-1], f[i + (1<<(j-1))][j-1]);
  142.     }
  143.     while(q--)
  144.     {
  145.         int x,y,z,t; cin >> x >> y >> z >> t;
  146.         int u = get(x,y);
  147.         int v = get(z,t);
  148.         int ans = inf;
  149.         while(head[u] != head[v]){
  150.             if(depth[head[u]] < depth[head[v]]) swap(u,v);
  151.             ans = min(ans, gett(pos[head[u]], pos[u]));
  152.             u = parent[head[u]];
  153.         }
  154.         if(depth[u] > depth[v]) swap(u,v);
  155.         ans = min(ans, gett(pos[u], pos[v]));
  156.         cout << ans << '\n';
  157.     }
  158. }
  159.  
  160. int main()
  161. {
  162.     ios_base::sync_with_stdio(0); cin.tie(0);
  163.     nhap();
  164.     make_tree();
  165.     dfs(root,-1);
  166.     decompose(root, -1, root);
  167.     process();
  168.     return 0;
  169. }
  170.  
Success #stdin #stdout 0.01s 18560KB
comments (?)
stdin
copy 
5 2
8 4 1 2 4
2 3 5 6 5
1 2 1 5 2
9 5 8 4 7
4 5 1 3 9
1 1 4 1
1 4 3 2
stdout
copy 
3
2
https://ideone.com/c5Komf
language:
C++14 (gcc 8.3)
created:
3 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!