Submission #767003

#	Time	Username	Problem	Language	Result	Execution time	Memory
767003		elkernos	Maze (JOI23_ho_t3)	C++17	0 / 100	0 ms	212 KiB

Main

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;

void __print(int x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << "'" << x << "'"; }
void __print(const char *x) { cerr << '"' << x << '"'; }
void __print(const string &x) { cerr << '"' << x << '"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
    cerr << '{';
    __print(x.first);
    cerr << ", ";
    __print(x.second);
    cerr << '}';
}
template <typename T>
void __print(const T &x)
{
    int f = 0;
    cerr << '{';
    for (auto &i : x)
        cerr << (f++ ? ", " : ""), __print(i);
    cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
    __print(t);
    if (sizeof...(v)) cerr << ", ";
    _print(v...);
}
#ifdef LOCAL
#define debug(x...)               \
    cerr << "[" << #x << "] = ["; \
    _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;
const int oo = 1e9 + 7;
const int mx = 2500;

void solve()
{
    int n, m, k;
    cin >> n >> m >> k;
    T s, e;
    cin >> s.first >> s.second;
    cin >> e.first >> e.second;
    vector a(n + 1, vector<char>(m + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            a[i][j] = getchar_unlocked();
        }
    }
    auto in = [&](T ss) {
        return ss.first >= 1 && ss.second >= 1 && ss.first <= n && ss.second <= m;
    };
    queue<T> q, q2;
    vector<bitset<mx>> tab(m + 1);
    for (int j = 1; j <= m; j++) {
        tab[j].set();
    }
    vector<int> X = {-1, 1, 0, 0};
    vector<int> Y = {0, 0, -1, 1};
    vector dist(n + 1, vector<int>(m + 1, oo));
    dist[s.first][s.second] = 0;
    q.push(s);
    tab[s.second].set(s.first, 0);
    while (dist[e.first][e.second] == oo) {
        while ((int)q.size()) {
            auto v = q.front();
            q.pop();
            for (int ck = 0; ck < 4; ck++) {
                T x = {v.first + X[ck], v.second + Y[ck]};
                if (!in(x)) continue;
                if (a[x.first][x.second] == '.') {
                    if (dist[x.first][x.second] == oo) {
                        dist[x.first][x.second] = dist[v.first][v.second];
                        tab[x.second].set(x.first, 0);
                        q.push(x);
                    }
                }
            }
            q2.push(v);
        }
        auto v = q2.front();
        q2.pop();
        for (int i = max(1, v.second - k); i <= min(m, v.second + k); i++) {
            int from = (i == v.second - k || i == v.second + k ? max(1, v.first - k + 1) : max(1, v.first - k));
            int to = (i == v.second - k || i == v.second + k ? min(n, v.first + k - 1) : min(n, v.first + k));
            for (int now = tab[i]._Find_next(from - 1); now <= to; now = tab[i]._Find_next(now)) {
                dist[now][i] = dist[v.first][v.second] + 1;
                tab[i].set(now, 0);
                q.push({now, i});
            }
        }
    }
    cout << dist[e.first][e.second] << "\n";
}

int32_t main()
{
    solve();
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 19
• Subtask 3: 0 / 16
• Subtask 4: 0 / 19
• Subtask 5: 0 / 5
• Subtask 6: 0 / 19
• Subtask 7: 0 / 8
• Subtask 8: 0 / 6