Submission #1089797

#TimeUsernameProblemLanguageResultExecution timeMemory
1089797_callmelucianMaze (JOI23_ho_t3)C++14
0 / 100
1 ms508 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pl; typedef pair<int,int> pii; typedef tuple<int,int,int> tt; #define all(a) a.begin(), a.end() #define filter(a) a.erase(unique(all(a)), a.end()) const int mn = 2e7 + 4e6 + 6; int leaf[2][mn], n, m; const int dr[4] = {-1, 0, 0, 1}; const int dc[4] = {0, -1, 1, 0}; void build (int layer, int k, int l, int r) { if (l == r) return leaf[layer][k] = l, void(); int mid = (l + r) >> 1; build(layer, 2 * k, l, mid); build(layer, 2 * k + 1, mid + 1, r); } void getNode (int k, int l, int r, int a, int b, vector<int> &vec) { if (b < l || r < a) return; if (a <= l && r <= b) return vec.push_back(k), void(); int mid = (l + r) >> 1; getNode(2 * k, l, mid, a, b, vec); getNode(2 * k + 1, mid + 1, r, a, b, vec); } int distance (int i, int j, int u, int v) { return max(abs(i - u), abs(j - v)); } bool ok (int i, int j) { if (i < 1 || j < 1) return 0; if (i > n || j > m) return 0; return 1; } int getInt() { int num = 0; char ch = getchar(); while (ch < '0' || ch > '9') { ch = getchar(); } while (ch >= '0' && ch <= '9') { num = (num << 3) + (num << 1) + (ch - '0'); ch = getchar(); } return num; } int main() { n = getInt(), m = getInt(); int k = getInt(); int stx = getInt(), sty = getInt(), enx = getInt(), eny = getInt(); vector<vector<bool>> block(n + 1, vector<bool>(m + 1)); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { char c = getchar(); if (c == '#') block[i][j] = 1; } } build(0, 1, 1, n); build(1, 1, 1, m); vector<vector<vector<int>>> dist(3); dist[1] = vector<vector<int>>(4 * n, vector<int>(m + 1, INT_MAX)); dist[2] = vector<vector<int>>(n + 1, vector<int>(4 * m, INT_MAX)); dist[0] = vector<vector<int>>(n + 1, vector<int>(m + 1, INT_MAX)); vector<vector<vector<bool>>> vis(3); vis[1] = vector<vector<bool>>(4 * n, vector<bool>(m + 1)); vis[2] = vector<vector<bool>>(n + 1, vector<bool>(4 * m)); vis[0] = vector<vector<bool>>(n + 1, vector<bool>(m + 1)); deque<tt> q; q.emplace_back(0, stx, sty); dist[0][stx][sty] = 0; while (q.size()) { int layer, x, y; tie(layer, x, y) = q.front(); q.pop_front(); if (vis[layer][x][y]) continue; vis[layer][x][y] = 1; function<void(int,int,int,int)> addEdge = [&] (int nlay, int nx, int ny, int w) { if (dist[layer][x][y] + w >= dist[nlay][nx][ny]) return; dist[nlay][nx][ny] = dist[layer][x][y] + w; if (w) q.emplace_back(nlay, nx, ny); else q.emplace_front(nlay, nx, ny); }; if (layer == 0) { if (block[x][y]) { if (distance(x, y, enx, eny) < k) return printf("%d", dist[layer][x][y]), 0; vector<int> nodeX, nodeY; int xL = max(1, x - k), xR = min(n, x + k), yL = max(1, y - k), yR = min(m, y + k); getNode(1, 1, n, max(1, x - k + 1), min(n, x + k - 1), nodeX); getNode(1, 1, m, max(1, y - k + 1), min(m, y + k - 1), nodeY); for (int u : nodeX) { addEdge(1, u, yL, 0); addEdge(1, u, yR, 0); } for (int v : nodeY) { addEdge(2, xL, v, 0); addEdge(2, xR, v, 0); } } else { if (distance(x, y, enx, eny) == 0) return printf("%d", dist[layer][x][y]), 0; for (int k = 0; k < 4; k++) if (ok(x + dr[k], y + dc[k])) addEdge(0, x + dr[k], y + dc[k], block[x + dr[k]][y + dc[k]]); } } else if (layer == 1) { if (leaf[0][x]) addEdge(0, leaf[0][x], y, block[leaf[0][x]][y]); else { addEdge(1, 2 * x, y, 0); addEdge(1, 2 * x + 1, y, 0); } } else if (layer == 2) { if (leaf[1][y]) addEdge(0, x, leaf[1][y], block[x][leaf[1][y]]); else { addEdge(2, x, 2 * y, 0); addEdge(2, x, 2 * y + 1, 0); } } } 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...