Submission #932882

#	Time	Username	Problem	Language	Result	Execution time	Memory
932882		Pring	Maze (JOI23_ho_t3)	C++17	0 / 100	2091 ms	1549072 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(pii p) {
        FOR(d, 0, 4) {
            pii nxt = p + D[d];
            if (OUT(nxt)) continue;
            if (s[p.fs][p.sc] == '.' && s[nxt.fs][nxt.sc] == '.') PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(0, nxt.fs, nxt.sc), 0);
            PUSH_EDGE(cvt3(0, p.fs, p.sc), cvt3(1, nxt.fs, nxt.sc), 1);
        }
    }

    void E1(pii p) {
        int l = max(0, p.fs - (N - 1)), r = min(R, p.fs + N);
        int y = p.sc, sr = cvt3(1, p.fs, p.sc);
        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);
    }

    void E2(pii p) {
        PUSH_EDGE(cvt3(2, p.fs, p.sc), cvt3(4, p.fs, p.sc), 0);
        if (p.fs == R - 1 || (p.fs + 1) % K == 0) return;
        PUSH_EDGE(cvt3(2, p.fs, p.sc), cvt3(2, p.fs + 1, p.sc), 0);
    }

    void E3(pii p) {
        PUSH_EDGE(cvt3(3, p.fs, p.sc), cvt3(4, p.fs, p.sc), 0);
        if (p.fs % K == 0) return;
        PUSH_EDGE(cvt3(3, p.fs, p.sc), cvt3(3, p.fs - 1, p.sc), 0);
    }

    void E4(pii p) {
        int l = max(0, p.sc - (N - 1)), r = min(C, p.sc + N);
        int x = p.fs, sr = cvt3(4, p.fs, p.sc);
        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);
    }

    void E5(pii p) {
        PUSH_EDGE(cvt3(5, p.fs, p.sc), cvt3(7, p.fs, p.sc), 0);
        if (p.sc + 1 == C || (p.sc - 1) % K == 0) return;
        PUSH_EDGE(cvt3(5, p.fs, p.sc), cvt3(5, p.fs, p.sc + 1), 0);
    }

    void E6(pii p) {
        PUSH_EDGE(cvt3(6, p.fs, p.sc), cvt3(7, p.fs, p.sc), 0);
        if (p.sc % K == 0) return;
        PUSH_EDGE(cvt3(6, p.fs, p.sc), cvt3(6, p.fs, p.sc - 1), 0);
    }

    void E7(pii p) {
        PUSH_EDGE(cvt3(7, p.fs, p.sc), cvt3(0, p.fs, p.sc), 0);
        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(int id) {
        int l = id / (C * R);
        pii p = cvt(id % (C * R));
        // debug(l, p.fs, p.sc);
        if (l == 0) E0(p);
        else if (l == 1) E1(p);
        else if (l == 2) E2(p);
        else if (l == 3) E3(p);
        else if (l == 4) E4(p);
        else if (l == 5) E5(p);
        else if (l == 6) E6(p);
        else E7(p);
    }
}

namespace BFS {
    vector<pii> v0, v1;
    void GO(int sr, int to) {
        fill(dis, dis + R * C * LAYER, -1);
        v0.push_back(mp(0, sr));
        while (v0.size()) {
            for (int i = 0; i < v0.size(); i++) {
                pii now = v0[i];
                if (dis[now.sc] != -1) continue;
                int len = now.fs, id = now.sc;
                dis[id] = len;
                // debug(len, id);
                if (id == to) return;
                EDGE::BUILD(id);
                for (auto &i : edge[id]) {
                    int tg = (i < 0 ? ~i : i);
                    if (dis[tg] != -1) continue;
                    if (i < 0) v1.push_back(mp(len + 1, tg));
                    else v0.push_back(mp(len, tg));
                }
            }
            swap(v0, v1);
            v1.clear();
        }
    }
}

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), cvt(to));
    cout << dis[cvt(to)] << '\n';
}

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

Compilation message (stderr)

Main.cpp: In function 'void BFS::GO(int, int)':
Main.cpp:154:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  154 |             for (int i = 0; i < v0.size(); i++) {
      |                             ~~^~~~~~~~~~~

• 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