結果

問題 No.2786 RMQ on Grid Path
ユーザー OTTFFOTTFF
提出日時 2024-06-15 14:37:09
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 346 ms / 6,000 ms
コード長 4,461 bytes
コンパイル時間 2,734 ms
コンパイル使用メモリ 219,980 KB
実行使用メモリ 35,772 KB
最終ジャッジ日時 2024-06-15 14:37:22
合計ジャッジ時間 12,595 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 346 ms
32,696 KB
testcase_13 AC 328 ms
32,416 KB
testcase_14 AC 325 ms
32,704 KB
testcase_15 AC 336 ms
32,832 KB
testcase_16 AC 311 ms
32,456 KB
testcase_17 AC 306 ms
33,472 KB
testcase_18 AC 342 ms
31,932 KB
testcase_19 AC 317 ms
32,492 KB
testcase_20 AC 318 ms
32,136 KB
testcase_21 AC 342 ms
32,056 KB
testcase_22 AC 198 ms
26,568 KB
testcase_23 AC 195 ms
26,312 KB
testcase_24 AC 263 ms
35,772 KB
testcase_25 AC 290 ms
33,472 KB
testcase_26 AC 258 ms
35,512 KB
testcase_27 AC 103 ms
16,036 KB
testcase_28 AC 93 ms
16,888 KB
testcase_29 AC 246 ms
26,032 KB
testcase_30 AC 91 ms
16,392 KB
testcase_31 AC 16 ms
5,376 KB
testcase_32 AC 226 ms
30,144 KB
testcase_33 AC 59 ms
8,572 KB
testcase_34 AC 243 ms
25,016 KB
testcase_35 AC 230 ms
25,148 KB
testcase_36 AC 252 ms
25,024 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();

using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;

template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) { 
    return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) { 
    return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z 
    if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
    if(x<z) { y=x; x=z; } else if(y<z) y=z; }

// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
struct UF {
  int n;
  vector<int> fa;
  UF(int n_=0):n(n_),fa(n_) { 
    for(int i=0;i<n;i++) fa[i]=i;
  }
  void init(int n_) {
    n=n_; fa.assign(n,0);
    for(int i=0;i<n;i++) fa[i]=i;
  }
  int find(int x) { return x==fa[x] ? x : fa[x]=find(fa[x]); }
  bool same(int x,int y) { return find(x)==find(y); }
  bool merge(int x,int y) {
    x=find(x); y=find(y);
    if(x==y) return false;
    fa[x]=y;
    return true;
  }
  vector<vector<int>> getgrps() {
    vector<int> id(n, -1);
    vector<vector<int> > grps;
    for (int i = 0; i < n; i++) {
      if (id[find(i)] == -1) {
        id[find(i)] = grps.size();
        grps.emplace_back();
      }
      grps[id[find(i)]].push_back(i);
    }
    return grps;
  }
};
template<typename Func> struct YCombinatorResult {
  Func func;
  template<typename T>
  explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
  template<class ...Args> decltype(auto) operator()(Args &&...args) {
    return func(std::ref(*this), std::forward<Args>(args)...);
  }
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
  return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/

int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};

void solve() {
  int n, m; cin >> n >> m;
  int nv = n * m;
  vector<vector<int>> a(n, vector<int>(m));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> a[i][j];
    }
  }
  auto getid = [&](int x, int y) -> int {
    return x * m + y;
  };
  // auto getpos = [&](int id) -> PII {
  //   return {id / m, id % m};
  // };

  int q; cin >> q;
  vector<vector<PII>> qs(nv);
  int stx, sty, edx, edy;
  int u, v;
  for (int i = 0; i < q; i++) {
    cin >> stx >> sty >> edx >> edy;
    stx--; sty--; edx--; edy--;
    u = getid(stx, sty); 
    v = getid(edx, edy);

    qs[u].push_back({v, i});
    qs[v].push_back({u, i});
  }

  vector<PII> rk;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      rk.push_back({i, j});
    }
  }
  sort(rk.begin(), rk.end(), [&](const PII& x, const PII& y){
    return a[x.first][x.second] < a[y.first][y.second];
  });

  vector<int> ans(q, -1);
  UF uf(nv);
  auto smart_merge = [&](int u, int v, int nans) {
    // cerr << "merging " << u << ' ' << v << ' ' << nans << endl;

    // merge qs:
    int f = 0;
    // always merge u into v
    if (qs[u].size() > qs[v].size()) {
      f = 1;
      swap(u, v);
    }

    int vid = uf.find(v);
    for (auto&& [qv, id] : qs[u]) {
      // cerr << " q " << qv << ' ' << id << endl;
      if (uf.find(qv) == vid) {
        // cerr << "addressed!" << endl;
        if (ans[id] == -1) ans[id] = nans;
      } else {
        qs[v].push_back({qv, id});
      }
    }
    if (f) {
      f = 0;
      swap(qs[u], qs[v]);
    }
  };

  vector<vector<int>> vis(n, vector<int>(m));
  for (auto&& [x, y] : rk) {
    vis[x][y] = 1;
    int id = getid(x, y);
    for (int i = 0; i < 4; i++) {
      int nx = x + dx[i], ny = y + dy[i];

      if (nx < 0 || n <= nx || ny < 0 || m <= ny || !vis[nx][ny]) continue;

      int idv = uf.find(getid(nx, ny));
      if (uf.merge(idv, id)) {
        smart_merge(idv, id, a[x][y]);
      }
    }
  }

  for (int i = 0; i < q; i++) {
    cout << ans[i] << '\n';
  }
}

int main() {
  int t = 1; 
  // cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
0