Submission #924188

#	Time	Username	Problem	Language	Result	Execution time	Memory
924188		ErJ	Maze (JOI23_ho_t3)	C++17	100 / 100	776 ms	340772 KiB

Main

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

#define ll long long
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define vs vector<string>
#define vc vector<char>
#define vb vector<bool>
#define vp vector<pair<ll, ll>>
#define pp pair<ll, ll>
#define qi queue<ll>
#define qp queue<pp>
#define pqi priority_queue<ll>
#define pqp priority_queue<pp>
#define mi map<ll, ll>
#define mpi map<pp, ll>
#define mip map<ll, pp>
#define mpp map<pp, pp>
#define mb map<ll, bool>
#define si set<ll>
#define sp set<pp>
#define mod 1000000007
#define rep(a, b) for(int a = 0; a < (b); a++)
#define inf 100000000111111111


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int r, s, n;
    qi q;
    cin >> r >> s >> n;
    int startr, starts, endr, ends;
    cin >> startr >> starts >> endr >> ends;
    startr--; starts--; ends--; endr--;
    vvi table(r), dist(r), distbfs(r);
    rep(i, r) {
        table[i].resize(s);
        dist[i].resize(s);
        distbfs[i].resize(s);
        rep(j, s) {
            char ch;
            cin >> ch;
            if (ch == '.') {
                table[i][j] = 0;
            }
            else {
                table[i][j] = -1;
            }
            dist[i][j] = inf;
            distbfs[i][j] = 0;
        }
    }
    vp sousedi = { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
    vp sousedi2 = { {0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1} };
    vp prevdist;
    qp q1;
    q1.push({startr, starts});
    
    while (!q1.empty()) {
        pp x = q1.front();
        q1.pop();
        dist[x.first][x.second] = 0;
        prevdist.push_back(x);
        for (pp i : sousedi) {
            ll a = x.first + i.first;
            ll b = x.second + i.second;
            if (a < r && a >= 0 && b < s && b >= 0) {
                if (table[a][b] == 0 && dist[a][b] == inf) {
                    q1.push({ a, b });
                    dist[a][b] = 0;
                }
            }
        }
    }
    ll pomoc = 0;
    while (dist[endr][ends] == inf) {
        /*rep(i, r) {
            rep(j, s) {
                cout << dist[i][j] << " ";
            }
            cout << endl;
        }*/
        pomoc++;
        qp q2;
        for (int i = 0; i < prevdist.size(); i++) {
            for (pp j : sousedi) {
                ll a = prevdist[i].first + j.first;
                ll b = prevdist[i].second + j.second;
                if (a < r && a >= 0 && b < s && b >= 0) {
                    if (dist[a][b] == inf && distbfs[a][b] != n) {
                        q2.push({ a, b });
                        distbfs[a][b] = n;
                    }
                }
            }
        }
        /*rep(i, r) {
            rep(j, s) {
                cout << distbfs[i][j] << " ";
            }
            cout << endl;
        }*/
        //cout << endl;
        prevdist.clear();
        while (!q2.empty()) {
            pp x = q2.front();
            prevdist.push_back(x);
            q2.pop();
            dist[x.first][x.second] = pomoc;
            if (distbfs[x.first][x.second] <= 1) {
                continue;
            }
            ll xd = distbfs[x.first][x.second];
            for (pp i : sousedi2) {
                ll a = x.first + i.first;
                ll b = x.second + i.second;
                if (a < r && a >= 0 && b < s && b >= 0) {
                    if (dist[a][b] == inf && distbfs[a][b] == 0) {
                        dist[a][b] = pomoc;
                        q2.push({ a, b });
                        distbfs[a][b] = xd - 1;
                    }
                }
            }
        }
        qp q3;
        rep(i, prevdist.size()) {
            q3.push(prevdist[i]);
        }
        while (!q3.empty()) {
            pp x = q3.front();
            q3.pop();
            for (pp i : sousedi) {
                ll a = x.first + i.first;
                ll b = x.second + i.second;
                if (a < r && a >= 0 && b < s && b >= 0) {
                    if (dist[a][b] == inf && table[a][b] == 0) {
                        q3.push({ a, b });
                        dist[a][b] = pomoc;
                        prevdist.push_back({ a, b });
                    }
                }
            }
        }
    }
    cout << dist[endr][ends] << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |         for (int i = 0; i < prevdist.size(); i++) {
      |                         ~~^~~~~~~~~~~~~~~~~
Main.cpp:24:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 | #define rep(a, b) for(int a = 0; a < (b); a++)
      |                                    ^
Main.cpp:129:9: note: in expansion of macro 'rep'
  129 |         rep(i, prevdist.size()) {
      |         ^~~

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