Submission #1253988

#TimeUsernameProblemLanguageResultExecution timeMemory
1253988LucaLucaMMaze (JOI23_ho_t3)C++20
51 / 100
2081 ms271424 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> #include <set> using ll = long long; #define debug(x) #x << " = " << x << '\n' const int INF = 1e9; const int dx[4] = {-1, 0, +1, 0}; const int dy[4] = {0, -1, 0, +1}; struct Fenwick2D { std::vector<std::vector<int>> aib; int n, m; void init(int _n, int _m) { n = _n + 2; m = _m + 2; aib = std::vector<std::vector<int>>(n + 3, std::vector<int>(m + 3, 0)); } void update(int x, int y, int v) { x++, y++; for (int i = x; i < n; i += i & -i) { for (int j = y; j < m; j += j & -j) { aib[i][j] += v; } } } int query(int x, int y) { x++, y++; int ret = 0; for (int i = x; i > 0; i -= i & -i) { for (int j = y; j > 0; j -= j & -j) { ret += aib[i][j]; } } return ret; } int pointQuery(int i, int j) { return query(i, j) - query(i, j - 1) - query(i - 1, j) + query(i - 1, j - 1); } int querySubmatrix(int x1, int y1, int x2, int y2) { return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1); } std::vector<std::pair<int, int>> findAll(int x1, int y1, int x2, int y2) { x1++, y1++, x2++, y2++; std::vector<std::pair<int, int>> ret; int i = x1; while (querySubmatrix(i - 1, y1 - 1, x2 - 1, y2 - 1)) { int l = i, r = x2; while (l < r) { int mid = (l + r) / 2; if (querySubmatrix(i - 1, y1 - 1, mid - 1, y2 - 1)) { r = mid; } else { l = mid + 1; } } int p = y1; int steps2 = querySubmatrix(i - 1, y1 - 1, i - 1, y2 - 1); while (steps2--) { int l = p, r = y2; while (l < r) { int mid = (l + r) / 2; if (querySubmatrix(i - 1, p - 1, i - 1, mid - 1)) { r = mid; } else { l = mid + 1; } } ret.push_back({i, r}); p = r + 1; } i++; } return ret; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(0); int n, m, k; std::cin >> n >> m >> k; int x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; x1--, y1--, x2--, y2--; std::vector<std::vector<int>> a(n, std::vector<int>(m)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char c; std::cin >> c; if (c == '.') { a[i][j] = 0; } else { a[i][j] = 1; } } } std::vector<std::set<std::pair<int, int>>> thisDistance(n * m + 2); std::vector<std::vector<int>> dist(n, std::vector<int>(m, +INF)); dist[x1][y1] = 0; thisDistance[0].insert({x1, y1}); Fenwick2D DS; DS.init(n, m); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { DS.update(i, j, +1); } } auto removeSubmatrix = [&](int x1, int y1, int x2, int y2, int d) { x1 = std::max(x1, 0); y1 = std::max(y1, 0); x2 = std::min(x2, n - 1); y2 = std::min(y2, m - 1); if (x1 > x2 || y1 > y2) { return; } auto ret = DS.findAll(x1, y1, x2, y2); for (auto [x, y] : ret) { x--, y--; assert(DS.pointQuery(x, y) == 1); DS.update(x, y, -1); dist[x][y] = d + 1; thisDistance[d + 1].insert({x, y}); } }; for (int d = 0; d <= n * m; d++) { std::set<std::pair<int, int>> st; auto dfs = [&](auto &&self, int x, int y) -> void { st.insert({x, y}); for (int dir = 0; dir < 4; dir++) { int xx = x + dx[dir], yy = y + dy[dir]; if (0 <= xx && xx < n && 0 <= yy && yy < m && dist[xx][yy] > d && !a[xx][yy]) { dist[xx][yy] = d; self(self, xx, yy); } } }; for (const auto &[x, y] : thisDistance[d]) { if (dist[x][y] < d) { continue; } dfs(dfs, x, y); st.insert({x, y}); } if (st.count({x2, y2})) { std::cout << d; return 0; } for (const auto &[x, y] : st) { if (DS.pointQuery(x, y) == 1) { DS.update(x, y, -1); } } for (const auto &[x, y] : st) { removeSubmatrix(x - (k - 1), y - k, x + (k - 1), y + k, d); removeSubmatrix(x - k, y - (k - 1), x - k, y + (k - 1), d); removeSubmatrix(x + k, y - (k - 1), x + k, y + (k - 1), d); } } std::cout << dist[x2][y2]; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...