oj.uz

Submission #932882

# Submission time Handle Problem Language Result Execution time Memory
932882 2024-02-24T10:43:53 Z Pring Maze (JOI23_ho_t3) C++17
0 / 100
 2000 ms 1549072 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 1128628 KB Output is correct
2 Correct 503 ms 1128532 KB Output is correct
3 Correct 421 ms 1128888 KB Output is correct
4 Correct 428 ms 1128624 KB Output is correct
5 Correct 417 ms 1128588 KB Output is correct
6 Correct 419 ms 1128784 KB Output is correct
7 Correct 416 ms 1128636 KB Output is correct
8 Correct 417 ms 1128844 KB Output is correct
9 Correct 420 ms 1128728 KB Output is correct
10 Correct 418 ms 1128532 KB Output is correct
11 Correct 425 ms 1128460 KB Output is correct
12 Correct 415 ms 1128444 KB Output is correct
13 Correct 423 ms 1128556 KB Output is correct
14 Correct 415 ms 1128528 KB Output is correct
15 Correct 427 ms 1128772 KB Output is correct
16 Correct 415 ms 1128660 KB Output is correct
17 Correct 419 ms 1128788 KB Output is correct
18 Correct 413 ms 1128880 KB Output is correct
19 Correct 458 ms 1141840 KB Output is correct
20 Correct 440 ms 1139388 KB Output is correct
21 Correct 437 ms 1135160 KB Output is correct
22 Correct 462 ms 1143280 KB Output is correct
23 Correct 458 ms 1144928 KB Output is correct
24 Correct 444 ms 1143596 KB Output is correct
25 Correct 440 ms 1141076 KB Output is correct
26 Correct 413 ms 1130832 KB Output is correct
27 Correct 422 ms 1131412 KB Output is correct
28 Correct 438 ms 1137716 KB Output is correct
29 Correct 557 ms 1169908 KB Output is correct
30 Correct 449 ms 1139836 KB Output is correct
31 Correct 451 ms 1149812 KB Output is correct
32 Correct 544 ms 1168812 KB Output is correct
33 Correct 532 ms 1166672 KB Output is correct
34 Correct 504 ms 1170748 KB Output is correct
35 Correct 501 ms 1166536 KB Output is correct
36 Correct 497 ms 1154868 KB Output is correct
37 Correct 519 ms 1162868 KB Output is correct
38 Correct 428 ms 1136324 KB Output is correct
39 Execution timed out 2091 ms 1549072 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #2
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 1128788 KB Output is correct
2 Correct 421 ms 1128496 KB Output is correct
3 Correct 425 ms 1128612 KB Output is correct
4 Correct 422 ms 1128532 KB Output is correct
5 Correct 429 ms 1129120 KB Output is correct
6 Correct 435 ms 1128480 KB Output is correct
7 Correct 426 ms 1128608 KB Output is correct
8 Correct 430 ms 1128532 KB Output is correct
9 Correct 424 ms 1128528 KB Output is correct
10 Correct 427 ms 1128980 KB Output is correct
11 Correct 423 ms 1128784 KB Output is correct
12 Correct 433 ms 1128552 KB Output is correct
13 Incorrect 425 ms 1128848 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 1128612 KB Output is correct
2 Correct 429 ms 1128616 KB Output is correct
3 Correct 424 ms 1128532 KB Output is correct
4 Correct 426 ms 1128716 KB Output is correct
5 Correct 425 ms 1128604 KB Output is correct
6 Correct 425 ms 1128604 KB Output is correct
7 Correct 424 ms 1128736 KB Output is correct
8 Correct 418 ms 1128788 KB Output is correct
9 Correct 426 ms 1128752 KB Output is correct
10 Incorrect 420 ms 1128712 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 1128788 KB Output is correct
2 Correct 421 ms 1128496 KB Output is correct
3 Correct 425 ms 1128612 KB Output is correct
4 Correct 422 ms 1128532 KB Output is correct
5 Correct 429 ms 1129120 KB Output is correct
6 Correct 435 ms 1128480 KB Output is correct
7 Correct 426 ms 1128608 KB Output is correct
8 Correct 430 ms 1128532 KB Output is correct
9 Correct 424 ms 1128528 KB Output is correct
10 Correct 427 ms 1128980 KB Output is correct
11 Correct 423 ms 1128784 KB Output is correct
12 Correct 433 ms 1128552 KB Output is correct
13 Incorrect 425 ms 1128848 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 1128788 KB Output is correct
2 Correct 421 ms 1128496 KB Output is correct
3 Correct 425 ms 1128612 KB Output is correct
4 Correct 422 ms 1128532 KB Output is correct
5 Correct 429 ms 1129120 KB Output is correct
6 Correct 435 ms 1128480 KB Output is correct
7 Correct 426 ms 1128608 KB Output is correct
8 Correct 430 ms 1128532 KB Output is correct
9 Correct 424 ms 1128528 KB Output is correct
10 Correct 427 ms 1128980 KB Output is correct
11 Correct 423 ms 1128784 KB Output is correct
12 Correct 433 ms 1128552 KB Output is correct
13 Incorrect 425 ms 1128848 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 1128628 KB Output is correct
2 Correct 503 ms 1128532 KB Output is correct
3 Correct 421 ms 1128888 KB Output is correct
4 Correct 428 ms 1128624 KB Output is correct
5 Correct 417 ms 1128588 KB Output is correct
6 Correct 419 ms 1128784 KB Output is correct
7 Correct 416 ms 1128636 KB Output is correct
8 Correct 417 ms 1128844 KB Output is correct
9 Correct 420 ms 1128728 KB Output is correct
10 Correct 418 ms 1128532 KB Output is correct
11 Correct 425 ms 1128460 KB Output is correct
12 Correct 415 ms 1128444 KB Output is correct
13 Correct 423 ms 1128556 KB Output is correct
14 Correct 415 ms 1128528 KB Output is correct
15 Correct 427 ms 1128772 KB Output is correct
16 Correct 415 ms 1128660 KB Output is correct
17 Correct 419 ms 1128788 KB Output is correct
18 Correct 413 ms 1128880 KB Output is correct
19 Correct 458 ms 1141840 KB Output is correct
20 Correct 440 ms 1139388 KB Output is correct
21 Correct 437 ms 1135160 KB Output is correct
22 Correct 462 ms 1143280 KB Output is correct
23 Correct 458 ms 1144928 KB Output is correct
24 Correct 444 ms 1143596 KB Output is correct
25 Correct 440 ms 1141076 KB Output is correct
26 Correct 413 ms 1130832 KB Output is correct
27 Correct 422 ms 1131412 KB Output is correct
28 Correct 438 ms 1137716 KB Output is correct
29 Correct 557 ms 1169908 KB Output is correct
30 Correct 449 ms 1139836 KB Output is correct
31 Correct 451 ms 1149812 KB Output is correct
32 Correct 544 ms 1168812 KB Output is correct
33 Correct 532 ms 1166672 KB Output is correct
34 Correct 504 ms 1170748 KB Output is correct
35 Correct 501 ms 1166536 KB Output is correct
36 Correct 497 ms 1154868 KB Output is correct
37 Correct 519 ms 1162868 KB Output is correct
38 Correct 428 ms 1136324 KB Output is correct
39 Execution timed out 2091 ms 1549072 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 1128628 KB Output is correct
2 Correct 503 ms 1128532 KB Output is correct
3 Correct 421 ms 1128888 KB Output is correct
4 Correct 428 ms 1128624 KB Output is correct
5 Correct 417 ms 1128588 KB Output is correct
6 Correct 419 ms 1128784 KB Output is correct
7 Correct 416 ms 1128636 KB Output is correct
8 Correct 417 ms 1128844 KB Output is correct
9 Correct 420 ms 1128728 KB Output is correct
10 Correct 418 ms 1128532 KB Output is correct
11 Correct 425 ms 1128460 KB Output is correct
12 Correct 415 ms 1128444 KB Output is correct
13 Correct 423 ms 1128556 KB Output is correct
14 Correct 415 ms 1128528 KB Output is correct
15 Correct 427 ms 1128772 KB Output is correct
16 Correct 415 ms 1128660 KB Output is correct
17 Correct 419 ms 1128788 KB Output is correct
18 Correct 413 ms 1128880 KB Output is correct
19 Correct 458 ms 1141840 KB Output is correct
20 Correct 440 ms 1139388 KB Output is correct
21 Correct 437 ms 1135160 KB Output is correct
22 Correct 462 ms 1143280 KB Output is correct
23 Correct 458 ms 1144928 KB Output is correct
24 Correct 444 ms 1143596 KB Output is correct
25 Correct 440 ms 1141076 KB Output is correct
26 Correct 413 ms 1130832 KB Output is correct
27 Correct 422 ms 1131412 KB Output is correct
28 Correct 438 ms 1137716 KB Output is correct
29 Correct 557 ms 1169908 KB Output is correct
30 Correct 449 ms 1139836 KB Output is correct
31 Correct 451 ms 1149812 KB Output is correct
32 Correct 544 ms 1168812 KB Output is correct
33 Correct 532 ms 1166672 KB Output is correct
34 Correct 504 ms 1170748 KB Output is correct
35 Correct 501 ms 1166536 KB Output is correct
36 Correct 497 ms 1154868 KB Output is correct
37 Correct 519 ms 1162868 KB Output is correct
38 Correct 428 ms 1136324 KB Output is correct
39 Execution timed out 2091 ms 1549072 KB Time limit exceeded
40 Halted 0 ms 0 KB -

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 513 ms 1128628 KB Output is correct
2 Correct 503 ms 1128532 KB Output is correct
3 Correct 421 ms 1128888 KB Output is correct
4 Correct 428 ms 1128624 KB Output is correct
5 Correct 417 ms 1128588 KB Output is correct
6 Correct 419 ms 1128784 KB Output is correct
7 Correct 416 ms 1128636 KB Output is correct
8 Correct 417 ms 1128844 KB Output is correct
9 Correct 420 ms 1128728 KB Output is correct
10 Correct 418 ms 1128532 KB Output is correct
11 Correct 425 ms 1128460 KB Output is correct
12 Correct 415 ms 1128444 KB Output is correct
13 Correct 423 ms 1128556 KB Output is correct
14 Correct 415 ms 1128528 KB Output is correct
15 Correct 427 ms 1128772 KB Output is correct
16 Correct 415 ms 1128660 KB Output is correct
17 Correct 419 ms 1128788 KB Output is correct
18 Correct 413 ms 1128880 KB Output is correct
19 Correct 458 ms 1141840 KB Output is correct
20 Correct 440 ms 1139388 KB Output is correct
21 Correct 437 ms 1135160 KB Output is correct
22 Correct 462 ms 1143280 KB Output is correct
23 Correct 458 ms 1144928 KB Output is correct
24 Correct 444 ms 1143596 KB Output is correct
25 Correct 440 ms 1141076 KB Output is correct
26 Correct 413 ms 1130832 KB Output is correct
27 Correct 422 ms 1131412 KB Output is correct
28 Correct 438 ms 1137716 KB Output is correct
29 Correct 557 ms 1169908 KB Output is correct
30 Correct 449 ms 1139836 KB Output is correct
31 Correct 451 ms 1149812 KB Output is correct
32 Correct 544 ms 1168812 KB Output is correct
33 Correct 532 ms 1166672 KB Output is correct
34 Correct 504 ms 1170748 KB Output is correct
35 Correct 501 ms 1166536 KB Output is correct
36 Correct 497 ms 1154868 KB Output is correct
37 Correct 519 ms 1162868 KB Output is correct
38 Correct 428 ms 1136324 KB Output is correct
39 Execution timed out 2091 ms 1549072 KB Time limit exceeded
40 Halted 0 ms 0 KB -