Submission #859423

#TimeUsernameProblemLanguageResultExecution timeMemory
859423arbuzickMaze (JOI23_ho_t3)C++17
43 / 100
2082 ms709716 KiB
#pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2") #include <bits/stdc++.h> using namespace std; constexpr int R = 1 << 12; set<pair<int, int>> tree[R * 2]; void add(int pos, pair<int, int> val) { for (pos += R; pos > 0; pos /= 2) { tree[pos].insert(val); } } void del(int pos, pair<int, int> val) { for (pos += R; pos > 0; pos /= 2) { tree[pos].erase(val); } } pair<int, int> get_val(int l, int r, int x, int y) { l = max(l, 0); r = min(r, R); l += R; r += R; pair<int, int> ans = {-1, -1}; while (l < r) { if (l & 1) { auto it = tree[l].lower_bound({x, 0}); if (it != tree[l].end() && x <= it->first && it->first < y) { return *it; } l++; } if (r & 1) { --r; auto it = tree[r].lower_bound({x, 0}); if (it != tree[r].end() && x <= it->first && it->first < y) { return *it; } } l >>= 1; r >>= 1; } return ans; } void solve() { int r, c, n; cin >> r >> c >> n; int sx, sy; cin >> sx >> sy; sx--, sy--; int gx, gy; cin >> gx >> gy; gx--, gy--; vector<string> a(r); for (int i = 0; i < r; ++i) { cin >> a[i]; } for (int i = 0; i < r; ++i) { for (int j = 0; j < c; ++j) { add(i, {j, i}); } } vector<vector<int>> dp(r, vector<int>(c, r * c)); deque<pair<int, int>> dq; dp[sx][sy] = 0; del(sx, {sy, sx}); dq.push_back({sx, sy}); while (!dq.empty()) { auto [x, y] = dq.front(); dq.pop_front(); if (x > 0 && a[x - 1][y] == '.' && dp[x - 1][y] > dp[x][y]) { if (dp[x - 1][y] == r * c) { del(x - 1, {y, x - 1}); } dp[x - 1][y] = dp[x][y]; dq.push_front({x - 1, y}); } if (x + 1 < r && a[x + 1][y] == '.' && dp[x + 1][y] > dp[x][y]) { if (dp[x + 1][y] == r * c) { del(x + 1, {y, x + 1}); } dp[x + 1][y] = dp[x][y]; dq.push_front({x + 1, y}); } if (y > 0 && a[x][y - 1] == '.' && dp[x][y - 1] > dp[x][y]) { if (dp[x][y - 1] == r * c) { del(x, {y - 1, x}); } dp[x][y - 1] = dp[x][y]; dq.push_front({x, y - 1}); } if (y + 1 < c && a[x][y + 1] == '.' && dp[x][y + 1] > dp[x][y]) { if (dp[x][y + 1] == r * c) { del(x, {y + 1, x}); } dp[x][y + 1] = dp[x][y]; dq.push_front({x, y + 1}); } while (true) { auto p = get_val(x - n + 1, x + n, y - n, y + n + 1); if (p.first == -1) { break; } del(p.second, p); swap(p.first, p.second); dp[p.first][p.second] = dp[x][y] + 1; dq.push_back(p); } while (true) { auto p = get_val(x - n, x + n + 1, y - n + 1, y + n); if (p.first == -1) { break; } del(p.second, p); swap(p.first, p.second); dp[p.first][p.second] = dp[x][y] + 1; dq.push_back(p); } } cout << dp[gx][gy] << '\n'; } signed main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) { solve(); } 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...