結果

問題 No.2786 RMQ on Grid Path
ユーザー OTTFFOTTFF
提出日時 2024-06-15 14:29:19
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,438 bytes
コンパイル時間 3,103 ms
コンパイル使用メモリ 219,604 KB
実行使用メモリ 35,776 KB
最終ジャッジ日時 2024-06-15 14:29:32
合計ジャッジ時間 12,755 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 201 ms
26,316 KB
testcase_23 AC 195 ms
26,308 KB
testcase_24 WA -
testcase_25 WA -
testcase_26 WA -
testcase_27 WA -
testcase_28 WA -
testcase_29 WA -
testcase_30 WA -
testcase_31 WA -
testcase_32 AC 233 ms
30,020 KB
testcase_33 AC 59 ms
8,448 KB
testcase_34 AC 240 ms
25,012 KB
testcase_35 AC 253 ms
25,020 KB
testcase_36 AC 235 ms
25,152 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);
  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;
        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