結果
問題 | No.2786 RMQ on Grid Path |
ユーザー | ゼット |
提出日時 | 2024-06-14 22:35:16 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,350 bytes |
コンパイル時間 | 1,439 ms |
コンパイル使用メモリ | 102,864 KB |
実行使用メモリ | 36,724 KB |
最終ジャッジ日時 | 2024-06-14 22:35:28 |
合計ジャッジ時間 | 10,216 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | AC | 4 ms
6,940 KB |
testcase_03 | AC | 4 ms
6,944 KB |
testcase_04 | AC | 4 ms
6,940 KB |
testcase_05 | AC | 5 ms
6,940 KB |
testcase_06 | AC | 5 ms
6,944 KB |
testcase_07 | AC | 5 ms
6,940 KB |
testcase_08 | AC | 5 ms
6,944 KB |
testcase_09 | AC | 4 ms
6,944 KB |
testcase_10 | AC | 5 ms
6,944 KB |
testcase_11 | AC | 5 ms
6,944 KB |
testcase_12 | TLE | - |
testcase_13 | -- | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
testcase_36 | -- | - |
ソースコード
#include <iostream> #include <vector> #include <set> #include <queue> #include <algorithm> #include <cassert> using namespace std; class DSU { public: int n; vector<int> parent_or_size; DSU(int N) { n = N; parent_or_size.resize(N, -1); } int leader(int a) { assert(0 <= a && a < n); if (parent_or_size[a] < 0) { return a; } return parent_or_size[a] = leader(parent_or_size[a]); } int merge(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); int x = leader(a); int y = leader(b); if (x == y) { return x; } if (-parent_or_size[x] < -parent_or_size[y]) { swap(x, y); } parent_or_size[x] += parent_or_size[y]; parent_or_size[y] = x; return x; } bool same(int a, int b) { assert(0 <= a && a < n); assert(0 <= b && b < n); return leader(a) == leader(b); } int size(int a) { assert(0 <= a && a < n); return -parent_or_size[leader(a)]; } vector<vector<int>> groups() { vector<int> leader_buf(n); vector<int> group_size(n, 0); for (int i = 0; i < n; ++i) { leader_buf[i] = leader(i); ++group_size[leader_buf[i]]; } vector<vector<int>> result(n); for (int i = 0; i < n; ++i) { result[leader_buf[i]].push_back(i); } vector<vector<int>> result2; for (int i = 0; i < n; ++i) { if (!result[i].empty()) { result2.push_back(result[i]); } } return result2; } }; 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]; } } set<int> C; vector<pair<int, int>> q; int Q; cin >> Q; for (int i = 0; i < Q; ++i) { int a, b, c, d; cin >> a >> b >> c >> d; q.push_back({(a - 1) * W + (b - 1), (c - 1) * W + (d - 1)}); C.insert(i); } vector<vector<pair<int, int>>> L(H * W + 1); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (i < H - 1) { int x = A[i][j]; int y = A[i + 1][j]; int z = max(x, y); L[z].push_back({i * W + j, (i + 1) * W + j}); } if (j < W - 1) { int x = A[i][j]; int y = A[i][j + 1]; int z = max(x, y); L[z].push_back({i * W + j, i * W + j + 1}); } } } vector<int> result(Q, 0); DSU Z(H * W); for (int x = 1; x <= H * W; ++x) { if (L[x].empty()) continue; for (auto& B : L[x]) { int pos1 = B.first, pos2 = B.second; Z.merge(pos1, pos2); } vector<int> l; for (int k : C) { int p1 = q[k].first, p2 = q[k].second; if (Z.same(p1, p2)) { l.push_back(k); result[k] = x; } } for (int k : l) { C.erase(k); } } for (int i = 0; i < Q; ++i) { cout << result[i] << endl; } return 0; }