結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー a1048576
提出日時 2024-06-14 21:53:15
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,926 bytes
コンパイル時間 4,077 ms
コンパイル使用メモリ 246,536 KB
実行使用メモリ 434,012 KB
最終ジャッジ日時 2024-06-14 21:53:32
合計ジャッジ時間 12,915 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 10 TLE * 1 -- * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#include <atcoder/all> 
using namespace atcoder;
using mint = modint1000000007;
#define int long long
struct UnionFind {
  vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2
  UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
    for(int i = 0; i < N; i++) par[i] = i;
  }
  int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  void unite(int x, int y) { // xとyの木を併合
    int rx = root(x); //xの根をrx
    int ry = root(y); //yの根をry
    if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
    par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
  }
  bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
    int rx = root(x);
    int ry = root(y);
    return rx == ry;
  }
};

signed main() {
  int h,w;
  cin >> h >> w;
  vector<vector<int>> a(h,vector<int>(w));
  vector<vector<pair<int,int>>> f(250001);
  for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) cin >> a[i][j], f[a[i][j]].push_back({i,j});
  int e = 200;
  int m = 1250;
  vector<UnionFind> uf(e+1,UnionFind(h*w));
  UnionFind u(h*w);
  vector<vector<bool>> ok(h,vector<bool>(w,false));
  for(int i = 1; i <= 250000; i++) {
    int l = f[i].size();
    for(int j = 0; j < l; j++) {
      int x,y;
      tie(x,y) = f[i][j];
      ok[x][y] = true;
      if(x != 0 && ok[x-1][y]) u.unite((x-1)*w+y,x*w+y);
      if(x != h-1 && ok[x+1][y]) u.unite((x+1)*w+y,x*w+y);
      if(y != 0 && ok[x][y-1]) u.unite(x*w+y-1,x*w+y);
      if(y != w-1 && ok[x][y+1]) u.unite(x*w+y+1,x*w+y);
    }
    if(i%m == 0) uf[i/m] = u;
  }
  int Q;
  cin >> Q;
  vector<int> x1(Q),x2(Q),y1(Q),y2(Q);
  vector<vector<int>> d(e);
  for(int i = 0; i < Q; i++) {
    cin >> x1[i] >> y1[i] >> x2[i] >> y2[i];
    x1[i]--,x2[i]--,y1[i]--,y2[i]--;
    bool v = false;
    for(int j = 0; j < e; j++) {
      if(uf[j+1].same(x1[i]*w+y1[i],x2[i]*w+y2[i])) {
        d[j].push_back(i);
        break;
      }
    }
  }
  vector<int> ans(Q,1e18);
  UnionFind r(h*w);
  vector<vector<bool>> o(h,vector<bool>(w,false));
  for(int i = 1; i <= 250000; i++) {
    int l = f[i].size();
    for(int j = 0; j < l; j++) {
      int x,y;
      tie(x,y) = f[i][j];
      o[x][y] = true;
      if(x != 0 && o[x-1][y]) r.unite((x-1)*w+y,x*w+y);
      if(x != h-1 && o[x+1][y]) r.unite((x+1)*w+y,x*w+y);
      if(y != 0 && o[x][y-1]) r.unite(x*w+y-1,x*w+y);
      if(y != w-1 && o[x][y+1]) r.unite(x*w+y+1,x*w+y);
    }
    int L = d[(i-1)/m].size();
    for(int j = 0; j < L; j++) {
      int y = d[(i-1)/m][j];
      if(r.same(x1[y]*w+y1[y],x2[y]*w+y2[y])) ans[y] = min(ans[y],i);
    }
  }
  for(int i = 0; i < Q; i++) cout << ans[i] << endl;
}
0