結果

問題 No.2786 RMQ on Grid Path
コンテスト
ユーザー InTheBloom
提出日時 2024-06-15 13:11:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,523 bytes
コンパイル時間 3,506 ms
コンパイル使用メモリ 128,752 KB
実行使用メモリ 14,008 KB
最終ジャッジ日時 2024-06-15 13:11:56
合計ジャッジ時間 11,194 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 TLE * 1 -- * 32
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;
using ll = long long;

class UnionFind {
    private:
        vector<int> par, siz;
    public:
        UnionFind (int N) {
            reset(N);
        }

        int root (int u) {
            if (par[u] == u) return par[u];
            return par[u] = root(par[u]);
        }

        bool same (int u, int v) {
            return root(u) == root(v);
        }

        int unite (int u, int v) {
            int ru = root(u), rv = root(v);
            if (ru == rv) return ru;
            if (siz[rv] < siz[ru]) swap(ru, rv);
            siz[ru] += siz[rv];
            par[rv] = ru;
            return ru;
        }

        int size (int u) {
            return siz[root(u)];
        }

        void reset (int N) {
            par.resize(N);
            siz.resize(N);
            for (int i = 0; i < N; i++) {
                par[i] = i;
                siz[i] = 1;
            }
        }
};

int main () {
    int H, W; cin >> H >> W;
    vector<vector<int>> A(H, vector<int>(W));
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) cin >> A[i][j];

    auto conv = [&](int i, int j) {
        return i * W + j;
    };

    // 並列二分探索
    // 先に時間ごとに見る頂点をまとめておく

    vector<vector<pair<int, int>>> time(H * W + 1);
    for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) time[A[i][j]].push_back(make_pair(i, j));

    int Q; cin >> Q;
    vector<tuple<int, int, int, int>> query(Q);
    for (int i = 0; i < Q; i++) {
        int rs, cs, rt, ct; cin >> rs >> cs >> rt >> ct;
        rs--, cs--, rt--, ct--;
        query[i] = make_tuple(rs, cs, rt, ct);
    }

    vector<int> ok(Q, H * W + 1), ng(Q, 0), mid(Q);
    vector<int> index(Q);
    const vector<pair<int, int>> dxy = {
        make_pair(0, 1),
        make_pair(1, 0),
        make_pair(0, -1),
        make_pair(-1, 0),
    };
    auto is_in = [&] (int i, int j) {
        return 0 <= i && i < H && 0 <= j && j < W;
    };

    UnionFind uf(H * W + 1);
    while (true) {
        for (int i = 0; i < Q; i++) {
            mid[i] = (ok[i] + ng[i]) / 2;
            index[i] = i;
        }
        sort(index.begin(), index.end(), [&](int x, int y) { return mid[x] < mid[y]; });

        // 時間を進めながら各クエリに回答
        uf.reset(H * W + 1);
        int lat = 0;

        for (int t = 1; t <= H * W; t++) {
            // uniteしていく
            for (auto [i, j] : time[t]) {
                for (auto [dy, dx] : dxy) {
                    int ni = i + dy, nj = j + dx;
                    if (!is_in(ni, nj)) continue;
                    if (t < A[ni][nj]) continue;
                    uf.unite(conv(i, j), conv(ni, nj));
                }
            }

            // クエリの二分探索を行う
            while (lat < index.size() && mid[index[lat]] == t) {
                auto [rs, cs, rt, ct] = query[index[lat]];
                if (uf.same(conv(rs, cs), conv(rt, ct))) {
                    ok[index[lat]] = mid[index[lat]];
                }
                else {
                    ng[index[lat]] = mid[index[lat]];
                }
                lat++;
            }
        }

        bool end = true;
        for (int i = 0; i < Q; i++) {
            if (1 < abs(ok[i] - ng[i])) end = false;
        }
        if (end) break;
    }

    for (int i = 0; i < Q; i++) {
        cout << ok[i] << "\n";
    }

    return 0;
}
0