結果

問題 No.2786 RMQ on Grid Path
ユーザー InTheBloomInTheBloom
提出日時 2024-06-15 14:12:07
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 2,064 ms / 6,000 ms
コード長 3,550 bytes
コンパイル時間 1,984 ms
コンパイル使用メモリ 128,140 KB
実行使用メモリ 24,492 KB
最終ジャッジ日時 2024-06-15 14:12:48
合計ジャッジ時間 38,615 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 3 ms
6,944 KB
testcase_03 AC 3 ms
6,940 KB
testcase_04 AC 3 ms
6,940 KB
testcase_05 AC 3 ms
6,940 KB
testcase_06 AC 3 ms
6,944 KB
testcase_07 AC 3 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 3 ms
6,940 KB
testcase_12 AC 2,019 ms
23,612 KB
testcase_13 AC 2,044 ms
23,644 KB
testcase_14 AC 1,997 ms
23,740 KB
testcase_15 AC 2,013 ms
23,548 KB
testcase_16 AC 2,055 ms
23,524 KB
testcase_17 AC 2,016 ms
23,612 KB
testcase_18 AC 2,064 ms
23,760 KB
testcase_19 AC 2,026 ms
23,712 KB
testcase_20 AC 1,971 ms
23,764 KB
testcase_21 AC 1,980 ms
23,696 KB
testcase_22 AC 1,736 ms
23,552 KB
testcase_23 AC 1,752 ms
23,552 KB
testcase_24 AC 750 ms
20,636 KB
testcase_25 AC 745 ms
20,680 KB
testcase_26 AC 752 ms
20,696 KB
testcase_27 AC 484 ms
10,240 KB
testcase_28 AC 398 ms
9,572 KB
testcase_29 AC 1,712 ms
20,916 KB
testcase_30 AC 400 ms
9,344 KB
testcase_31 AC 56 ms
6,940 KB
testcase_32 AC 596 ms
20,248 KB
testcase_33 AC 155 ms
9,472 KB
testcase_34 AC 872 ms
24,104 KB
testcase_35 AC 857 ms
24,492 KB
testcase_36 AC 879 ms
23,924 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

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), 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 = 0; 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