fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3. #define pii pair <int, int>
  4. #define fi first
  5. #define se second
  6. //#define int long long
  7. #define el cout << endl;
  8. #define spc(n) fixed << setprecision(n)
  9. #define ed cout << "\n__________________________________\n"
  10. #define IOS ios_base::sync_with_stdio(0);  cin.tie(0); cout.tie(0);
  11. using namespace std;
  12.  
  13.  
  14. const int N = 505;
  15. const int oo = 1e9;
  16.  
  17.  
  18. int n, q, lim;
  19. int a[N][N], dist[N][N];
  20.  
  21. int dx[] = {0, 0, -1, 1};
  22. int dy[] = {1, -1, 0, 0};
  23.  
  24. bool check(int s, int t, int e1, int e2, int mid)
  25. {
  26.     queue <pii> q;
  27.     for (int i = 1; i <= n; i++)
  28.         for (int j = 1; j <= n; j++)
  29.             dist[i][j] = oo;
  30.  
  31.     q.push({s, t});
  32.     dist[s][t] = 0;
  33.  
  34.     while(q.size())
  35.     {
  36.         int u = q.front().fi;
  37.         int v = q.front().se;
  38.         q.pop();
  39.  
  40.         for (int k = 0; k < 4; k++)
  41.         {
  42.             int x = u + dx[k];
  43.             int y = v + dy[k];
  44.             if (x < 1 || x > n || y < 1 || y > n || a[x][y] < mid) continue;
  45.             if (dist[x][y] > dist[u][v] + 1)
  46.             {
  47.                 dist[x][y] = dist[u][v] + 1;
  48.                 q.push({x, y});
  49.             }
  50.         }
  51.     }
  52.  
  53.     return dist[e1][e2] != oo;
  54. }
  55.  
  56.  
  57. void sub12()
  58. {
  59.     while(q--)
  60.     {
  61.         int u, v, x, y;
  62.         cin >> u >> v >> x >> y;
  63.  
  64.         int l = 1, r = lim, ans = lim;
  65.         while(l <= r)
  66.         {
  67.             int mid = (l + r) >> 1;
  68.             if (check(u, v, x, y, mid))
  69.             {
  70.                 ans = mid;
  71.                 l = mid + 1;
  72.             }
  73.             else r = mid - 1;
  74.         }
  75.         cout << ans << endl;
  76.     }
  77. }
  78.  
  79.  
  80. struct graph
  81. {
  82.     int u, v, w;
  83. };  vector <graph> edge;
  84.  
  85. struct cmpw
  86. {
  87.     bool operator()(const graph &x, const graph &y)
  88.     const
  89.     {
  90.         return x.w > y.w;
  91.     }
  92. };
  93.  
  94. const int LOG = 18;
  95. const int M = 260000;
  96. int cnt;
  97. int par[M], high[M], p[M][20], mn[M][20], node[N][N];
  98. vector <pii> g[M];
  99.  
  100. void makeset()
  101. {
  102.     for (int i = 1; i <= n * n; i++) par[i] = i;
  103. }
  104.  
  105. int findset(int u)
  106. {
  107.     if (par[u] == u) return u;
  108.     return (par[u] = findset(par[u]));
  109. }
  110.  
  111. void DSU(int u, int v, int w)
  112. {
  113.     int x = findset(u), y = findset(v);
  114.     if (x == y) return;
  115.     par[y] = x;
  116.     g[u].push_back({v, w});
  117.     g[v].push_back({u, w});
  118. }
  119.  
  120. void DFS(int u, int par)
  121. {
  122.     for (pii x : g[u])
  123.     {
  124.         int v = x.fi, w = x.se;
  125.         if (v == par) continue;
  126.         high[v] = high[u] + 1;
  127.         p[v][0] = u;
  128.         mn[v][0] = w;
  129.         DFS(v, u);
  130.     }
  131. }
  132.  
  133. void init()
  134. {
  135.     for (int j = 1; j <= LOG; j++)
  136.         for (int i = 1; i <= n * n; i++)
  137.         {
  138.             p[i][j] = p[p[i][j - 1]][j - 1];
  139.             mn[i][j] = min(mn[i][j - 1], mn[p[i][j - 1]][j - 1]);
  140.         }
  141. }
  142.  
  143. void setup()
  144. {
  145.     int cnt = 0;
  146.     for (int i = 1; i <= n; i++)
  147.         for (int j = 1; j <= n; j++)
  148.             node[i][j] = ++cnt;
  149.  
  150.     for (int i = 1; i <= n; i++)
  151.         for (int j = 1; j <= n; j++)
  152.         {
  153.             int u = node[i][j];
  154.             for (int k = 0; k < 4; k++)
  155.             {int x = i + dx[k];
  156.                 int y = j + dy[k];
  157.                 if (x < 1 || x > n || y < 1 || y > n) continue;
  158.                 int v = node[x][y];
  159.                 int w = min(a[i][j], a[x][y]);
  160.                 edge.push_back({u, v, w});
  161.             }
  162.         }
  163.  
  164.     makeset();
  165.     sort(edge.begin(), edge.end(), cmpw());
  166.     for (graph x : edge)
  167.     {
  168.         int u = x.u, v = x.v, w = x.w;
  169.         DSU(u, v, w);
  170.     }
  171.  
  172.     DFS(1, -1);
  173.     init();
  174. }
  175.  
  176. int LCA(int u, int v)
  177. {
  178.     int ans = oo;
  179.     if (high[u] < high[v]) swap(u, v);
  180.     int h = high[u] - high[v];
  181.     for (int i = LOG; i >= 0; i--)
  182.         if ((h >> i) & 1)
  183.         {
  184.             ans = min(ans, mn[u][i]);
  185.             u = p[u][i];
  186.         }
  187.     if (u == v) return ans;
  188.  
  189.     for (int i = LOG; i >= 0; i--)
  190.         if (p[u][i] != p[v][i])
  191.         {
  192.             ans = min(ans, mn[u][i]);
  193.             ans = min(ans, mn[v][i]);
  194.             u = p[u][i];
  195.             v = p[v][i];
  196.         }
  197.     return ans = min({ans, mn[u][0], mn[v][0]});
  198. }
  199.  
  200. void sub34()
  201. {
  202.     setup();
  203.     while(q--)
  204.     {
  205.         int u, v, x, y;
  206.         cin >> u >> v >> x >> y;
  207.         cout << LCA(node[u][v], node[x][y]) << endl;
  208.     }
  209. }
  210.  
  211. signed main ()
  212. {
  213.     // freopen("file.inp", "r", stdin);
  214.     // freopen("file.out", "w", stdout);
  215.     IOS;
  216.     cin >> n >> q;
  217.     for (int i = 1; i <= n; i++)
  218.         for (int j = 1; j <= n; j++)
  219.         {
  220.             cin >> a[i][j];
  221.             lim = max(lim, a[i][j]);
  222.         }
  223.  
  224. //    if (n <= 100 && q <= 2000) sub12();
  225. //    else
  226.     sub34();
  227.  
  228.     return 0;
  229. }
  230.  
Success #stdin #stdout 0.01s 12932KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IUOWtJ
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!