| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 825493 |
2023-08-14T23:23:39 Z |
null_awe |
Maze (JOI23_ho_t3) |
C++14 |
|
1 ms |
468 KB |
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
struct Segtree {
int n;
vector<bool> on;
Segtree() {}
Segtree(int n) : n(n), on(4 * n, 1) {}
void upd(int t, int tl, int tr, int p) {
if (tl == tr) on[t] = false;
else {
int m = (tl + tr) / 2;
if (p <= m) upd(2 * t, tl, m, p);
else upd(2 * t + 1, m + 1, tr, p);
on[t] = on[2 * t] | on[2 * t + 1];
}
}
int qry(int t, int tl, int tr, int l, int r) {
l = max(l, tl), r = min(r, tr);
if (l > r) return -1;
if (tl == l && tr == r && !on[t]) return -1;
if (tl == tr) {
assert(on[t]);
return tl;
}
int m = (tl + tr) / 2;
int f = qry(2 * t, tl, m, l, r);
if (f >= 0) return f;
return qry(2 * t + 1, m + 1, tr, l, r);
}
};
struct Groups {
int r, c;
vector<Segtree> rs, cs;
Groups() {}
Groups(int r, int c) : r(r), c(c) {
for (int i = 0; i < r; ++i) {
Segtree tmp(c);
rs.push_back(tmp);
}
for (int i = 0; i < c; ++i) {
Segtree tmp(r);
cs.push_back(tmp);
}
}
void upd(int x, int y) {
// cout << x << ' ' << y << endl;
rs[x].upd(1, 0, c - 1, y);
cs[y].upd(1, 0, r - 1, x);
// cout << "done" << endl;
}
int qrow(int row, int l, int rr) {
if (row < 0 || row >= r) return -1;
return rs[row].qry(1, 0, c - 1, max(l, 0), min(rr, c - 1));
}
int qcol(int col, int l, int rr) {
if (col < 0 || col >= c) return -1;
return cs[col].qry(1, 0, r - 1, max(l, 0), min(rr, r - 1));
}
};
int main() {
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> arr(r);
for (int i = 0; i < r; ++i) cin >> arr[i];
// . = empty
// # = wall
Groups groups(r, c);
vector<vector<int>> dists(r, vector<int>(c, INT_MAX));
dists[sx][sy] = 0;
// cout << dists[gx][gy] << '\n';
groups.upd(sx, sy);
// cout << groups.qrow(sx, sy, sy) << endl;
vector<pii> q; q.push_back({sx, sy});
queue<pii> rq; for (pii _p : q) rq.push(_p);
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
rq.push({nx, ny});
q.push_back({nx, ny});
dists[nx][ny] = dists[xx][yy];
groups.upd(nx, ny);
}
}
while (q.size()) {
// for (int i = 0; i < r; ++i) {
// for (int j = 0; j < c; ++j) cout << dists[i][j] << ' ';
// cout << endl;
// }
// break;
// cout << "here" << endl;
// break;
vector<pii> nq;
for (pii p : q) {
int x = p.first, y = p.second;
// cout << x << ' ' << y << '\n';
if (x > 0 && dists[x - 1][y] <= dists[x][y]) {
// cout << "t1" << endl;
// query up:
int cur;
while ((cur = groups.qrow(x + n, y - n + 1, y + n - 1)) != -1) {
nq.push_back({x + n, cur});
dists[x + n][cur] = dists[x][y] + 1;
groups.upd(x + n, cur);
}
if (x + n - 1 < r && y - n >= 0 && dists[x + n - 1][y - n] == INT_MAX) {
nq.push_back({x + n - 1, y - n});
dists[x + n - 1][y - n] = dists[x][y] + 1;
groups.upd(x + n - 1, y - n);
}
if (x + n - 1 < r && y + n < c && dists[x + n - 1][y - n] == INT_MAX) {
nq.push_back({x + n - 1, y + n});
dists[x + n - 1][y + n] = dists[x][y] + 1;
groups.upd(x + n - 1, y + n);
}
} else if (x < r - 1 && dists[x + 1][y] <= dists[x][y]) {
// cout << "t2" << endl;
// query down:
int cur;
while ((cur = groups.qrow(x - n, y - n + 1, y + n - 1)) != -1) {
nq.push_back({x - n, cur});
dists[x - n][cur] = dists[x][y] + 1;
groups.upd(x - n, cur);
}
if (x - n + 1 >= 0 && y - n >= 0 && dists[x - n + 1][y - n] == INT_MAX) {
nq.push_back({x - n + 1, y - n});
dists[x - n + 1][y - n] = dists[x][y] + 1;
groups.upd(x - n + 1, y - n);
}
if (x - n + 1 >= 0 && y + n < c && dists[x - n + 1][y - n] == INT_MAX) {
nq.push_back({x - n + 1, y + n});
dists[x - n + 1][y + n] = dists[x][y] + 1;
groups.upd(x - n + 1, y + n);
}
} else if (y > 0 && dists[x][y - 1] <= dists[x][y]) {
// cout << "t3" << endl;
// query left:
int cur;
while ((cur = groups.qcol(y + n, x - n + 1, x + n - 1)) != -1) {
nq.push_back({cur, y + n});
dists[cur][y + n] = dists[x][y] + 1;
groups.upd(cur, y + n);
}
if (y + n - 1 < c && x - n >= 0 && dists[x - n][y + n - 1] == INT_MAX) {
nq.push_back({x - n, y + n - 1});
dists[x - n][y + n - 1] = dists[x][y] + 1;
groups.upd(x - n, y + n - 1);
}
if (y + n - 1 < c && x + n < r && dists[x + n][y + n - 1] == INT_MAX) {
nq.push_back({x + n, y + n - 1});
dists[x + n][y + n - 1] = dists[x][y] + 1;
groups.upd(x + n, y + n - 1);
}
} else if (y < r - 1 && dists[x][y + 1] <= dists[x][y]) {
// cout << "t4" << endl;
// query right:
int cur;
while ((cur = groups.qcol(y - n, x - n + 1, x + n - 1)) != -1) {
nq.push_back({cur, y - n});
dists[cur][y - n] = dists[x][y] + 1;
groups.upd(cur, y - n);
}
if (y - n + 1 >= 0 && x - n >= 0 && dists[x - n][y - n + 1] == INT_MAX) {
nq.push_back({x - n, y - n + 1});
dists[x - n][y - n + 1] = dists[x][y] + 1;
groups.upd(x - n, y - n + 1);
}
if (y - n + 1 >= 0 && x + n < r && dists[x + n][y - n + 1] == INT_MAX) {
nq.push_back({x + n, y - n + 1});
dists[x + n][y - n + 1] = dists[x][y] + 1;
groups.upd(x + n, y - n + 1);
}
} else {
// query all:
for (int i = -n; i <= n; ++i) {
int cx = x + i, cyl = y - n, cyr = y + n;
if (abs(i) == n) ++cyl, --cyr;
int cur;
while ((cur = groups.qrow(cx, cyl, cyr)) != -1) {
nq.push_back({cx, cur});
dists[cx][cur] = dists[x][y] + 1;
groups.upd(cx, cur);
}
}
}
}
queue<pii> rq; for (pii _p : nq) rq.push(_p);
while (rq.size()) {
pii front = rq.front(); rq.pop();
int xx = front.first, yy = front.second;
for (int d = 0; d < 4; ++d) {
int nx = xx + dx[d], ny = yy + dy[d];
if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
if (dists[nx][ny] < INT_MAX || arr[nx][ny] == '#') continue;
rq.push({nx, ny});
nq.push_back({nx, ny});
dists[nx][ny] = dists[xx][yy];
groups.upd(nx, ny);
}
}
q = nq;
}
assert(dists[gx][gy] != INT_MAX);
cout << dists[gx][gy] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
0 ms |
304 KB |
Output is correct |
| 4 |
Correct |
1 ms |
300 KB |
Output is correct |
| 5 |
Correct |
0 ms |
300 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Incorrect |
1 ms |
300 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
0 ms |
296 KB |
Output is correct |
| 5 |
Correct |
1 ms |
212 KB |
Output is correct |
| 6 |
Correct |
1 ms |
224 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
216 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
