| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1089780 |
2024-09-17T06:42:43 Z |
_callmelucian |
Maze (JOI23_ho_t3) |
C++14 |
|
1328 ms |
2097152 KB |
#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 (x == enx && y == eny)
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
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 time |
Memory |
Grader output |
| 1 |
Runtime error |
1313 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1270 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1328 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1270 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1270 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1313 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1313 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1313 ms |
2097152 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
