| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 839449 |
2023-08-30T04:10:59 Z |
dong_liu |
Maze (JOI23_ho_t3) |
C++17 |
|
0 ms |
340 KB |
#pragma GCC optimize("O3,unroll-loops")
#include "bits/stdc++.h"
using namespace std;
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif
const int NM = 6e6;
typedef pair<int, int> pi;
struct Range {
int *p, n; bool *rem;
Range(int n) : n(n) {
p = (int *) malloc(n * sizeof(int));
rem = (bool *) malloc(n * sizeof(bool));
for (int i = 0; i < n; i++) p[i] = i, rem[i] = false;
}
int dsf(int i) {
return p[i] == i ? i : p[i] = dsf(p[i]);
}
void dsj(int i, int j) { p[dsf(i)] = dsf(j); }
bool has(int i) { return !rem[i]; }
void remove(int i) {
if (i > 0 && rem[i-1]) dsj(i-1, i);
if (i+1 < n && rem[i+1]) dsj(i, i+1);
rem[i] = 1;
}
int next(int i) {
return i == n ? n : !rem[i] ? i : dsf(i)+1;
}
};
int main() {
ios::sync_with_stdio(false);
cin.exceptions(cin.failbit);
cin.tie(NULL);
int k, n, m;
cin >> n >> m >> k;
int i1, j1, i2, j2;
cin >> i1 >> j1 >> i2 >> j2, i1--, j1--, i2--, j2--;
static char g[NM+1];
for (int i = 0; i < n; i++) cin >> g[i*m];
vector<Range> row, col;
for (int i = 0; i < n; i++) row.push_back(Range(m));
for (int i = 0; i < m; i++) col.push_back(Range(n));
static int d[NM];
static bool fl[NM];
vector<pi> f;
d[i1*m+j1] = 0, f.push_back({i1, j1}), row[i1].remove(j1), col[j1].remove(i1);
for (int x = 0; ; x++) {
for (int p = 0; p < int(f.size()); p++) {
auto [i,j] = f[p];
fl[i*m+j] = true;
if (i == i2 && j == j2) {
cout << x << '\n';
return 0;
}
if (i > 0 && g[(i-1)*m+j] == '.' && d[(i-1)*m+j] == -1)
d[(i-1)*m+j] = x, f.push_back({i-1,j}), row[i-1].remove(j), col[j].remove(i-1);
if (i+1 < n && g[(i+1)*m+j] == '.' && d[(i+1)*m+j] == -1)
d[(i+1)*m+j] = x, f.push_back({i+1,j}), row[i+1].remove(j), col[j].remove(i+1);
if (j > 0 && g[i*m+j-1] == '.' && d[i*m+j-1] == -1)
d[i*m+j-1] = x, f.push_back({i,j-1}), row[i].remove(j-1), col[j-1].remove(i);
if (j+1 < m && g[i*m+j+1] == '.' && d[i*m+j+1] == -1)
d[i*m+j+1] = x, f.push_back({i,j+1}), row[i].remove(j+1), col[j+1].remove(i);
}
vector<pi> half = f, g;
for (auto [i,j] : f) {
int p = row[i].next(max(0,j-k));
while (p < m && p <= j+k) {
d[i*m+p] = x+1;
if (abs(p-j) != k) {
row[i].remove(p), col[p].remove(i);
fl[i*m+p] = true;
}
half.push_back({i,p}), g.push_back({i,p});
p = row[i].next(p+1);
}
}
for (auto [i,j] : half) if (row[i].has(j))
row[i].remove(j), col[j].remove(i);
for (auto [i,j] : half) {
int bound = k - (fl[i*m+j]?0:1);
int p = col[j].next(max(0,i-bound));
while (p < n && p <= i+bound) {
d[p*m+j] = x+1;
g.push_back({p,j});
row[p].remove(j), col[j].remove(p);
p = col[j].next(p+1);
}
}
f = move(g);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
