Submission #932829

#	Time	Username	Problem	Language	Result	Execution time	Memory
932829		Pring	Maze (JOI23_ho_t3)	C++17	0 / 100	452 ms	1129152 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#ifdef MIKU
#define debug(x...) cout << "[" << #x << "] : ", dout(x)
void dout() { cout << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif

// #define int long long
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
typedef pair<int, int> pii;

const int MXN = 6000005, LAYER = 8;
const pii D[4] = {mp(1, 0), mp(-1, 0), mp(0, 1), mp(0, -1)};
int R, C, N;
pii sr, to;
vector<string> s;
int K;
vector<int> edge[MXN * LAYER];
int dis[MXN * LAYER];

inline int cvt(pii p) {
    return p.fs * C + p.sc;
}

inline pii cvt(int x) {
    return mp(x / C, x % C);
}

inline pii operator+(pii a, pii b) {
    return mp(a.fs + b.fs, a.sc + b.sc);
}

inline bool OUT(pii p) {
    if (!(0 <= p.fs && p.fs < R)) return true;
    if (!(0 <= p.sc && p.sc < C)) return true;
    return false;
}

namespace EDGE {
    inline int cvt3(int l, int x, int y) {
        return l * R * C + x * C + y;
    }

    inline void PUSH_EDGE(int sr, int to, int val) {
        // debug(sr, to, val);
        edge[sr].push_back(val ? ~to : to);
    }

    void E0() {
        FOR(i, 0, R * C) {
            pii p = cvt(i);
            if (s[p.fs][p.sc] == '#') continue;
            FOR(d, 0, 4) {
                pii nxt = p + D[d];
                if (OUT(nxt)) continue;
                if (s[nxt.fs][nxt.sc] == '#') continue;
                PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
            }
        }
    }

    void E0_1() {
        FOR(i, 0, R * C) {
            pii p = cvt(i);
            FOR(d, 0, 4) {
                pii nxt = p + D[d];
                if (OUT(nxt)) continue;
                PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(1, nxt.fs, nxt.sc), 1);
            }
        }
    }

    void E23_4() {
        FOR(j, 0, C) {
            for (int l_bnd = 0, r_bnd; l_bnd < R; l_bnd += K) {
                r_bnd = min(R, l_bnd + K);
                FOR(i, l_bnd, r_bnd) {
                    PUSH_EDGE(cvt3(2, i, j), cvt3(4, i, j), 0);
                    PUSH_EDGE(cvt3(3, i, j), cvt3(4, i, j), 0);
                }
                FOR(i, l_bnd, r_bnd - 1) PUSH_EDGE(cvt3(2, i, j), cvt3(2, i + 1, j), 0);
                FOR(i, l_bnd + 1, r_bnd) PUSH_EDGE(cvt3(3, i, j), cvt3(3, i - 1, j), 0);
            }
        }
    }

    void E1_23() {
        auto ADD_EDGE = [&](int y, int l, int r, int sr) -> void {
            if (r - l == K) {
                PUSH_EDGE(sr, cvt3(2, l, y), 0);
                PUSH_EDGE(sr, cvt3(3, r - 1, y), 0);
                return;
            }
            if (r == R) {
                PUSH_EDGE(sr, cvt3(2, l, y), 0);
                int m = (l ? (l - 1) / K * K + K : 0);
                if (m < R) PUSH_EDGE(sr, cvt3(2, m, y), 0);
                return;
            }
            PUSH_EDGE(sr, cvt3(3, r - 1, y), 0);
        };
        FOR(j, 0, C) {
            FOR(i, 0, R) {
                int l_bnd = max(0, i - (N - 1)), r_bnd = min(R, i + N);
                ADD_EDGE(j, l_bnd, r_bnd, cvt3(1, i, j));
            }
        }
    }

    void E56_7() {
        FOR(i, 0, R) {
            for (int l_bnd = 0, r_bnd; l_bnd < C; l_bnd += K) {
                r_bnd = min(C, l_bnd + K);
                FOR(j, l_bnd, r_bnd) {
                    PUSH_EDGE(cvt3(5, i, j), cvt3(7, i, j), 0);
                    PUSH_EDGE(cvt3(6, i, j), cvt3(7, i, j), 0);
                }
                FOR(j, l_bnd, r_bnd - 1) PUSH_EDGE(cvt3(5, i, j), cvt3(5, i, j + 1), 0);
                FOR(j, l_bnd + 1, r_bnd) PUSH_EDGE(cvt3(6, i, j), cvt3(6, i, j - 1), 0);
            }
        }
    }

    void E4_56() {
        auto ADD_EDGE = [&](int x, int l, int r, int sr) -> void {
            if (r - l == K) {
                PUSH_EDGE(sr, cvt3(5, x, l), 0);
                PUSH_EDGE(sr, cvt3(6, x, r - 1), 0);
                return;
            }
            if (r == C) {
                PUSH_EDGE(sr, cvt3(5, x, l), 0);
                int m = (l ? (l - 1) / K * K + K : 0);
                if (m < C) PUSH_EDGE(sr, cvt3(5, x, m), 0);
                return;
            }
            PUSH_EDGE(sr, cvt3(6, x, r - 1), 0);
        };
        FOR(i, 0, R) {
            FOR(j, 0, C) {
                int l_bnd = max(0, j - (N - 1)), r_bnd = min(C, j + N);
                ADD_EDGE(i, l_bnd, r_bnd, cvt3(4, i, j));
            }
        }
    }

    void E7_0() {
        FOR(i, 0, R * C) {
            pii p = cvt(i);
            FOR(d, 0, 4) {
                pii nxt = p + D[d];
                if (OUT(nxt) || s[nxt.fs][nxt.sc] == '#') continue;
                PUSH_EDGE(cvt3(7, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
            }
        }
    }

    void BUILD() {
        E0();
        E0_1();
        E23_4();
        E1_23();
        E56_7();
        E4_56();
        E7_0();
    }
}

namespace BFS {
    deque<pii> dq;
    void GO(int sr) {
        fill(dis, dis + R * C * LAYER, -1);
        dq.push_back(mp(0, sr));
        while (dq.size()) {
            pii now = dq.front();
            dq.pop_front();
            // debug(now.fs, now.sc);
            if (dis[now.sc] != -1) continue;
            int len = now.fs, id = now.sc;
            dis[id] = len;
            for (auto &i : edge[id]) {
                int tg = (i < 0 ? ~i : i);
                if (dis[tg] != -1) continue;
                if (i < 0) dq.push_back(mp(len + 1, tg));
                else dq.push_front(mp(len, tg));
            }
        }
    }
}

void miku() {
    cin >> R >> C >> N >> sr.fs >> sr.sc >> to.fs >> to.sc;
    sr.fs--, sr.sc--, to.fs--, to.sc--;
    K = N * 2 - 1;
    s.resize(R);
    FOR(i, 0, R) cin >> s[i];
    EDGE::BUILD();
    BFS::GO(cvt(sr));
    cout << dis[cvt(to)] << '\n';
}

int32_t main() {
    cin.tie(0) -> sync_with_stdio(false);
    cin.exceptions(iostream::failbit);
    miku();
    return 0;
}

• 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