Submission #1181914

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181914		trufanov.p	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	47 ms	2376 KiB

adventure

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <set>

using namespace std;

typedef long long ll;

const int INF = 1e9;

#pragma GCC optimize ("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

int dx[4] = { 0, -1, 0, 1 };
int dy[4] = { -1, 0, 1, 0 };

inline int good(int x, int y, int n, int m) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> f(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j < m; ++j) {
            if (s[j] == 'W') {
                f[i][j] = 0;
            } else if (s[j] == 'N') {
                f[i][j] = 1;
            } else if (s[j] == 'E') {
                f[i][j] = 2;
            } else if (s[j] == 'S') {
                f[i][j] = 3;
            } else {
                f[i][j] = -1;
            }
        }
    }
    vector<vector<int>> d(n, vector<int>(m, INF));
    d[0][0] = 0;
    set<pair<int, pair<int, int>>> s;
    s.insert({ 0, {0, 0} });
    while (!s.empty()) {
        auto [x, y] = s.begin()->second;
        s.erase(s.begin());
        if (f[x][y] == -1) {
            continue;
        }
        for (int c = 0; c < 4; ++c) {
            int nx = x + dx[(f[x][y] + c) % 4], ny = y + dy[(f[x][y] + c) % 4];
            if (good(nx, ny, n, m) && d[nx][ny] > d[x][y] + c) {
                s.erase({ d[nx][ny], {nx, ny} });
                d[nx][ny] = d[x][y] + c;
                s.insert({ d[nx][ny], {nx, ny} });
            }
        }
    }
    cout << (d[n - 1][m - 1] == INF ? -1 : d[n - 1][m - 1]) << '\n';
}

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