Submission #1089787

#TimeUsernameProblemLanguageResultExecution timeMemory
1089787_callmelucianMaze (JOI23_ho_t3)C++14
0 / 100
1531 ms2097152 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 = 6e6 + 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 main() { freopen("MAZE.inp", "r", stdin); freopen("MAZE.out", "w", stdout); ios::sync_with_stdio(0); cin.tie(0); int k; cin >> n >> m >> k; int stx, sty, enx, eny; cin >> stx >> sty >> enx >> eny; 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; cin >> c; 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 cout << 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 + 1 - 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 cout << 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); } } } cout << -1; return 0; }

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:48:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |     freopen("MAZE.inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:49:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |     freopen("MAZE.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...