| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 776083 | 2023-07-07T09:29:38 Z | green_gold_dog | Maze (JOI23_ho_t3) | C++17 | 1 ms | 212 KB |
#include<bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1'000'000'000;
template<typename T>
bool assign_min(T& a, T b) {
if (a > b) {
a = b;
return true;
}
return false;
}
template<typename T>
bool assign_max(T& a, T b) {
if (a < b) {
a = b;
return true;
}
return false;
}
struct segment_tree {
vector<bool> tree;
ll size;
segment_tree(ll n) {
size = 1;
while (size < n) {
size *= 2;
}
tree.resize(size * 2, false);
}
vector<ll> set(ll l, ll r) {
vector<ll> ans;
set(1, 0, size, l, r, ans);
return ans;
}
void set(ll v, ll l, ll r, ll ql, ll qr, vector<ll>& ans) {
if (tree[v]) {
return;
}
if (r <= ql || qr <= l) {
return;
}
if (r - l == 1) {
ans.push_back(l);
tree[v] = true;
return;
}
ll mid = (l + r) / 2;
set(v * 2, l, mid, ql, qr, ans);
set(v * 2 + 1, mid, r, ql, qr, ans);
tree[v] = tree[v * 2] && tree[v * 2 + 1];
}
};
struct segment_tree_am {
vector<ll> m, tree;
ll size;
segment_tree_am(ll n) {
size = 1;
while (size < n) {
size *= 2;
}
m.resize(size * 2, 0);
tree.resize(size * 2, 0);
}
bool get(ll l, ll r) {
return get(1, 0, size, l, r);
}
bool get(ll v, ll l, ll r, ll ql, ll qr) {
if (tree[v] != 0) {
return false;
}
if (ql <= l && r <= qr) {
return true;
}
if (qr <= l || r <= ql) {
return false;
}
ll mid = (l + r) / 2;
return get(v * 2, l, mid, ql, qr) || get(v * 2 + 1, mid, r, ql, qr);
}
void add(ll l, ll r, ll x) {
add(1, 0, size, l, r, x);
}
void add(ll v, ll l, ll r, ll ql, ll qr, ll x) {
if (ql <= l && r <= qr) {
tree[v] += x;
m[v] += x;
return;
}
if (qr <= l || r <= ql) {
return;
}
ll mid = (l + r) / 2;
add(v * 2, l, mid, ql, qr, x);
add(v * 2 + 1, mid, r, ql, qr, x);
tree[v] = min(tree[v * 2], tree[v * 2 + 1]) + m[v];
}
ll find_first(ll l, ll r) {
if (!get(l, r)) {
return r;
}
return find_first(1, 0, size, l, r);
}
ll find_first(ll v, ll l, ll r, ll ql, ll qr) {
if (r - l == 1) {
return l;
}
ll mid = (l + r) / 2;
if (get(v * 2, l, mid, ql, qr)) {
return find_first(v * 2, l, mid, ql, qr);
} else {
return find_first(v * 2 + 1, mid, r, ql, qr);
}
}
};
void solve() {
ll n, r, c;
cin >> r >> c >> n;
ll sx, sy, gx, gy;
cin >> sx >> sy >> gx >> gy;
sx--;
sy--;
gx--;
gy--;
vector<vector<bool>> arr(r, vector<bool>(c, false));
vector<vector<bool>> used(r, vector<bool>(c, false));
vector<segment_tree> dist(r, segment_tree(c));
for (ll i = 0; i < r; i++) {
string s;
cin >> s;
for (ll j = 0; j < c; j++) {
if (s[j] == '.') {
arr[i][j] = true;
}
}
}
vector<pair<ll, ll>> now;
now.emplace_back(sx, sy);
used[sx][sy] = true;
ll na = 0;
while (true) {
vector<pair<ll, ll>> nu;
vector<vector<ll>> all(r * 2);
while (!now.empty()) {
auto[x, y] = now.back();
nu.emplace_back(x, y);
if (x == gx && y == gy) {
cout << na << '\n';
return;
}
now.pop_back();
if (x > 0 && arr[x - 1][y]) {
if (!used[x - 1][y]) {
used[x - 1][y] = true;
now.emplace_back(x - 1, y);
}
}
if (x + 1 < r && arr[x + 1][y]) {
if (!used[x + 1][y]) {
used[x + 1][y] = true;
now.emplace_back(x + 1, y);
}
}
if (y > 0 && arr[x][y - 1]) {
if (!used[x][y - 1]) {
used[x][y - 1] = true;
now.emplace_back(x, y - 1);
}
}
if (y + 1 < c && arr[x][y + 1]) {
if (!used[x][y + 1]) {
used[x][y + 1] = true;
now.emplace_back(x, y + 1);
}
}
all[max(x - n + 1, (ll)0) * 2].emplace_back(y);
all[(min(x + n, r) - 1) * 2 + 1].emplace_back(y);
}
na++;
for (auto[x, y] : nu) {
if (x - n >= 0) {
ll i = x - n;
for (auto j : dist[i].set(max(y - n + 1, (ll)0), min(y + n, c))) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
}
if (x + n < r) {
ll i = x + n;
for (auto j : dist[i].set(max(y - n + 1, (ll)0), min(y + n, c))) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
}
}
multiset<ll> nps;
set<pair<ll, ll>> no;
no.insert(make_pair(-INF, -INF));
for (ll i = 0; i < r; i++) {
for (auto y : all[i * 2]) {
nps.insert(y);
ll l = y - n, r = y + n + 1;
no.insert(make_pair(l, r));
continue;
auto io = no.upper_bound(make_pair(l, INF));
io--;
if (io->second >= r) {
continue;
}
auto it = nps.find(y);
ll prev = -INF, next = INF;
if (it != nps.begin()) {
it--;
prev = *it;
it++;
}
it++;
if (it != nps.end()) {
next = *it;
}
if (y - prev - 1 <= n * 2) {
l = io->first;
no.erase(io);
}
io = no.upper_bound(make_pair(l, INF));
if (next - y - 1 <= n * 2) {
r = io->second;
no.erase(io);
}
no.insert(make_pair(l, r));
}
for (auto[l, r] : no) {
for (auto j : dist[i].set(max(l, (ll)0), min(r, c))) {
if (!used[i][j]) {
used[i][j] = true;
now.emplace_back(i, j);
}
}
}
for (auto y : all[i * 2 + 1]) {
ll l = y - n, r = y + n + 1;
no.insert(make_pair(l, r));
continue;
auto io = no.upper_bound(make_pair(l, INF));
io--;
nps.erase(nps.find(y));
if (nps.empty()) {
no.erase(io);
continue;
}
auto[lo, ro] = *io;
auto it = nps.lower_bound(y);
if (it != nps.end() && *it == y) {
continue;
}
if (it == nps.end()) {
no.erase(io);
it--;
no.insert(make_pair(lo, *it + n + 1));
continue;
}
if (it == nps.begin()) {
no.erase(io);
no.insert(make_pair(*it - n, ro));
continue;
}
auto lit = it, rit = it;
lit--;
if (*rit - *lit - 1 <= n * 2) {
continue;
}
no.erase(io);
no.insert(make_pair(lo, *lit + n + 1));
no.insert(make_pair(*rit - n, ro));
}
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 0 ms | 212 KB | Output is correct |
| 2 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 3 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 212 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |