#988977 (C++14) No.2786 RMQ on Grid Path

提出ソース

結果

問題	No.2786 RMQ on Grid Path
ユーザー	OTTFF
提出日時	2024-06-15 09:41:24
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	411 ms / 6,000 ms
コード長	4,486 bytes
コンパイル時間	2,290 ms
コンパイル使用メモリ	189,640 KB
実行使用メモリ	79,744 KB
最終ジャッジ日時	2024-06-15 09:41:38
合計ジャッジ時間	13,388 ms
ジャッジサーバーID （参考情報）	judge5 / judge2

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,816 KB
testcase_01	AC	2 ms 6,944 KB
testcase_02	AC	2 ms 6,944 KB
testcase_03	AC	3 ms 6,940 KB
testcase_04	AC	2 ms 6,940 KB
testcase_05	AC	3 ms 6,940 KB
testcase_06	AC	2 ms 6,944 KB
testcase_07	AC	2 ms 6,940 KB
testcase_08	AC	2 ms 6,940 KB
testcase_09	AC	2 ms 6,944 KB
testcase_10	AC	2 ms 6,944 KB
testcase_11	AC	2 ms 6,940 KB
testcase_12	AC	385 ms 52,284 KB
testcase_13	AC	403 ms 52,520 KB
testcase_14	AC	366 ms 52,204 KB
testcase_15	AC	366 ms 52,428 KB
testcase_16	AC	383 ms 52,296 KB
testcase_17	AC	373 ms 52,068 KB
testcase_18	AC	408 ms 52,316 KB
testcase_19	AC	397 ms 52,284 KB
testcase_20	AC	371 ms 52,488 KB
testcase_21	AC	411 ms 52,356 KB
testcase_22	AC	257 ms 49,692 KB
testcase_23	AC	255 ms 49,424 KB
testcase_24	AC	314 ms 56,828 KB
testcase_25	AC	288 ms 56,872 KB
testcase_26	AC	287 ms 56,904 KB
testcase_27	AC	107 ms 15,008 KB
testcase_28	AC	86 ms 9,472 KB
testcase_29	AC	333 ms 48,452 KB
testcase_30	AC	88 ms 10,752 KB
testcase_31	AC	16 ms 5,632 KB
testcase_32	AC	246 ms 40,984 KB
testcase_33	AC	64 ms 7,292 KB
testcase_34	AC	321 ms 79,664 KB
testcase_35	AC	306 ms 79,704 KB
testcase_36	AC	303 ms 79,744 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In function 'void solve()':
main.cpp:120:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  120 |   for (auto&& [x, y] : rk) {
      |               ^
main.cpp: In lambda function:
main.cpp:152:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  152 |     for (auto&& [v, id] : qs[u]) {
      |                 ^
main.cpp:155:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17' [-Wc++17-extensions]
  155 |       auto [x, y] = getpos(uf.find(v));
      |            ^

ソースコード

raw source code

#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<vector<int>> vis(n, vector<int>(m));
  vector<vector<int>> g(nv);
  UF uf(nv);
  int rt = -1;
  for (auto&& [x, y] : rk) {
    vis[x][y] = 1;
    int id = getid(x, y);
    // cerr << "id " << id << ' ' << x << ' ' << y << endl;
    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) continue;

      if (!vis[nx][ny]) continue;

      int idv = uf.find(getid(nx, ny));
      if (uf.merge(idv, id)) {
        g[id].push_back(idv);
        // cerr << "add " << id << ' ' << idv << endl;
      }
    }
    rt = id;
  }

  uf.init(nv);
  vector<int> vis2(nv);
  vector<int> ans(q);
  y_comb([&](auto dfs, int u) -> void {
    // cerr << "dfs " << u << endl;
    vis2[u] = 1;

    for (int v : g[u]) {
      dfs(v);
      uf.merge(v, u);
    }

    for (auto&& [v, id] : qs[u]) {
      if (!vis2[v]) continue;
      // cerr << "solve " << u << ' ' << v << ' ' << id << ' ';
      auto [x, y] = getpos(uf.find(v));
      // cerr << x << ' ' << y << ' ' << a[x][y] << endl;
      ans[id] = a[x][y];
    }
  })(rt);

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

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

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード