Submission #951826

#	Time	Username	Problem	Language	Result	Execution time	Memory
951826		EJIC_B_KEDAX	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	268 ms	39656 KiB

adventure

#include <bits/stdc++.h>
#include <random>

#ifndef LOCAL
    //#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
typedef long long ll;
typedef double dd;
typedef long double ld;
typedef unsigned int uii;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

void solve();

mt19937_64 mt(1);

int32_t main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
#endif
    cout << fixed << setprecision(30);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        solve();
    }
}

pair<int, int> to[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool check(int i, int j, pair<int, int> s, vector<vector<int>>& a) {
    return a[i][j] != 4 && i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && a[i + s.x][j + s.y] != 4;
}

struct point {
    int i, j, w;
    point(int i1, int j1, int w1) {
        i = i1;
        j = j1;
        w = w1;
    }
};

bool operator < (const point& a, const point& b) {
    return a.w < b.w || (a.w == b.w && a.i < b.i) || (a.w == b.w && a.i == b.i && a.j < b.j);
}

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            char x;
            cin >> x;
            if (x == 'N') {
                a[i][j] = 0;
            } else if (x == 'E') {
                a[i][j] = 1;
            } else if (x == 'S') {
                a[i][j] = 2;
            } else if (x == 'W') {
                a[i][j] = 3;
            } else {
                a[i][j] = 4;
            }
        }
    }
    a[n - 1][m - 1] = 0;
    vector<vector<vector<point>>> g(n, vector<vector<point>>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            for (int l = 0; l < 4; l++) {
                if (check(i, j, to[l], a)) {
                    g[i][j].emplace_back(i + to[l].x, j + to[l].y, (l - a[i][j] + 4) % 4);
                }
            }
        }
    }
    vector<vector<int>> dist(n, vector<int>(m, INT32_MAX));
    dist[0][0] = 0;
    multiset<point> st;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            st.emplace(i, j, dist[i][j]);
        }
    }
    while (!st.empty()) {
        auto s = *st.begin();
        if (s.w == INT32_MAX) {
            break;
        }
        st.erase(st.begin());
        for (auto i : g[s.i][s.j]) {
            if (st.find({i.i, i.j, dist[i.i][i.j]}) != st.end()) {
                st.erase(st.find({i.i, i.j, dist[i.i][i.j]}));
                dist[i.i][i.j] = min(dist[i.i][i.j], dist[s.i][s.j] + i.w);
                st.emplace(i.i, i.j, dist[i.i][i.j]);
            }
        }
    }
    if (dist[n - 1][m - 1] == INT32_MAX) {
        cout << "-1\n";
        return;
    }
    cout << dist[n - 1][m - 1] << '\n';
}

Compilation message (stderr)

adventure.cpp: In function 'bool check(int, int, std::pair<int, int>, std::vector<std::vector<int> >&)':
adventure.cpp:45:52: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     return a[i][j] != 4 && i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && a[i + s.x][j + s.y] != 4;
      |                                            ~~~~~~~~^~~~~~~~~~
adventure.cpp:45:90: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     return a[i][j] != 4 && i + s.x >= 0 && i + s.x < a.size() && j + s.y >= 0 && j + s.y < a[i].size() && a[i + s.x][j + s.y] != 4;
      |                                                                                  ~~~~~~~~^~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50