Submission #1177923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177923		dzhoz0	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	50 / 100	2100 ms	144756 KiB

adventure

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

#define INF 1e9
#define f first
#define s second
#define pii pair<int, int>
#define vi vector<int>

const int MOD = 1'000'000'000 + 7;

void setIO(string name = "")
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
#ifdef LOCAL
    freopen("inp.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    if (!name.empty())
    {
        freopen((name + ".INP").c_str(), "r", stdin);
        freopen((name + ".OUT").c_str(), "w", stdout);
    }
#endif
}

const int reality[5] = {-1, 4, 2, 1, 3};
inline int cost(int k1, int k2) {
    return (reality[k2] - reality[k1] + 4) % 4; 
}

const vector<pii> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int n, m;
int a[505][505];

inline int cnv(int i, int j, int state) {
    return 5 * ((i - 1) * m + j) + state;
}

inline bool in(int i, int j) {
    return i >= 1 && i <= n && j >= 1 && j <= m;
}

unordered_map<int, vector<pii>> g;
unordered_map<int, int> d;
deque<int> buckets[4];

void dial(int source) {
    d.clear();
    d[source] = 0;
    buckets[0].push_back(source);

    int inBuckets = 1;

    while (inBuckets > 0) {
        int id = 0;
        while (id <= 3 && buckets[id].empty()) id++;
        if (id > 3) break;

        int u = buckets[id].front();
        buckets[id].pop_front();
        inBuckets--;

        if (d[u] < id) continue;

        for (auto [v, w] : g[u]) {
            int newDist = d[u] + w;
            if (!d.count(v) || newDist < d[v]) {
                d[v] = newDist;
                buckets[newDist % 4].push_back(v);
                inBuckets++;
            }
        }
    }
}

void solve() {
    cin >> n >> m;
    g.clear();
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            char c; cin >> c;
            a[i][j] = (c == 'X' ? 0 : c == 'W' ? 1 : c == 'E' ? 2 : c == 'N' ? 3 : 4);
        }
    }

    if (a[1][1] == 0 || a[n][m] != 0) {
        cout << -1 << '\n';
        return;
    }

    for (int state = 1; state <= 4; state++) {
        g[0].emplace_back(cnv(1, 1, state), 0);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i][j] == 0) continue;
            for (int k = 1; k <= 4; k++) {
                int x = i + directions[k - 1].f;
                int y = j + directions[k - 1].s;
                if (!in(x, y)) continue;
                
                for (int k1 = (a[x][y] != 0 ? 1 : 0); k1 <= (a[x][y] == 0 ? 0 : 4); k1++) {
                    g[cnv(i, j, k)].emplace_back(cnv(x, y, k1), cost(a[i][j], k));
                }
            }
        }
    }

    dial(0);

    if (!d.count(cnv(n, m, 0)) || d[cnv(n, m, 0)] == INF) {
        cout << -1 << '\n';
    } else {
        cout << d[cnv(n, m, 0)] << '\n';
    }
}

signed main()
{
    setIO();
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
}

Compilation message (stderr)

adventure.cpp: In function 'void setIO(std::string)':
adventure.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".INP").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
adventure.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen((name + ".OUT").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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