結果

問題 No.2786 RMQ on Grid Path
ユーザー a1048576a1048576
提出日時 2024-06-14 21:57:13
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 2,846 bytes
コンパイル時間 2,512 ms
コンパイル使用メモリ 191,796 KB
実行使用メモリ 529,864 KB
最終ジャッジ日時 2024-06-14 21:57:25
合計ジャッジ時間 11,637 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 7 ms
9,236 KB
testcase_01 AC 6 ms
9,136 KB
testcase_02 AC 14 ms
9,208 KB
testcase_03 AC 15 ms
9,256 KB
testcase_04 AC 14 ms
9,184 KB
testcase_05 AC 15 ms
9,184 KB
testcase_06 AC 15 ms
9,252 KB
testcase_07 AC 15 ms
9,456 KB
testcase_08 AC 14 ms
9,128 KB
testcase_09 AC 14 ms
9,120 KB
testcase_10 AC 14 ms
9,292 KB
testcase_11 AC 14 ms
9,432 KB
testcase_12 MLE -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#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 = 250;
  int m = 1000;
  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