Submission #1178242

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178242		dzhoz0	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	50 / 100	2017 ms	100572 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
}
// START OF DEBUG
#define db(val) "["#val" = "<<(val)<<"] "
#define print_op(...) ostream& operator<<(ostream& out, const __VA_ARGS__& u)
// for printing std::pair
template<class U, class V> print_op(pair<U, V>) {
    return out << "(" << u.first << ", " << u.second << ")";
}
// for printing collection
template<class Con, class = decltype(begin(declval<Con>()))>
typename enable_if<!is_same<Con, string>::value, ostream&>::type
operator<<(ostream& out, const Con& con) { 
    out << "{";
    for (auto beg = con.begin(), it = beg; it != con.end(); ++it)
        out << (it == beg ? "" : ", ") << *it;
    return out << "}";
}
// for printing std::tuple
template<size_t i, class T> ostream& print_tuple_utils(ostream& out, const T& tup) {
    if constexpr(i == tuple_size<T>::value) return out << ")"; 
    else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); 
}
template<class ...U> print_op(tuple<U...>) {
    return print_tuple_utils<0, tuple<U...>>(out, u);
}
// END OF DEBUG

const int reality[5] = {-1, 4, 2, 1, 3};

int cost(int k1, int k2) {
    // return k1 != k2;
    int res = (reality[k2] - reality[k1] + 4); 
    if(res >= 4) res -= 4;
    return res;
}
const int MAXN = 500;
const vector<pii> directions = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int n, m;
int a[MAXN + 1][MAXN + 1];
// 0 : no arrows
// 1234: LRUD

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

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

vector<pii> g[5 * MAXN * MAXN + 1];
int d[5 * MAXN * MAXN + 1];
queue<int> buckets[3 + 1];

void dial(int source) {
    fill(d, d + 5 * MAXN * MAXN + 1, INF);

    d[source] = 0;
    buckets[0].push(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();
        
        if(d[u] < id) continue;

        for(auto [v, w] : g[u]) {
            if(d[u] + w < d[v]) {
                d[v] = d[u] + w;
                buckets[d[v] % 4].push(v);
                inBuckets++;
            }
        }
    }
}

void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            char c; cin >> c;
            if(c == 'X') a[i][j] = 0;
            if(c == 'W') a[i][j] = 1;
            if(c == 'E') a[i][j] = 2;
            if(c == 'N') a[i][j] = 3;
            if(c == 'S') a[i][j] = 4;
            // cout << i << ' ' << j << ' ' << cnv(i, j, 4) << '\n';
        }
    }
    if(a[1][1] == 0 || a[n][m] != 0) {
        cout << -1 << '\n';
        return;
    }
    for(int state = 1; state <= 4; state++) {
        g[0].push_back({cnv(1, 1, state), 0});
    }
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= m; j++) {
            // for(pii d : directions) {
            //     int x = i + d.f;
            //     int y = j + d.s;
            //     if(!in(x, y)) continue;
            //     for(int s1 = !(a[i][j] == 0); s1 <= (a[i][j] == 0 ? 0 : 4); s1++) {
            //         for(int s2 = !(a[x][y] == 0); s2 <= (a[x][y] == 0 ? 0 : 4); s2++) {
            //             g[cnv(i, j, s1)].push_back({cnv(x, y, s2), s2 != a[x][y]});
            //         }
            //     }
            // }
            // cout << i << ' ' << j << '\n';
            if(a[i][j] == 0) continue;
            for(int k = 1; k <= 4; k++) {
                pii d = directions[k - 1];
                int x = i + d.f;
                int y = j + d.s;
                // cout << i << ' ' << j << ' ' << x << ' ' << y << '\n';
                if(!in(x, y)) continue;
                for(int k1 = (a[x][y] != 0); k1 <= (a[x][y] == 0 ? 0 : 4); k1++) {
                    // cout << db(i) << db(j) << db(k) << ' ' << db(x) << db(y) << db(k1) << ' ' << cost(a[i][j], k) << '\n';
                    // cout << cnv(i, j, k) << ' ' << cnv(x, y, k1) << '\n';
                    g[cnv(i, j, k)].push_back({cnv(x, y, k1), cost(a[i][j], k)});
                }
            }
        }
    }
    dial(0);
    if(d[cnv(n, m, 0)] == INF) {
        cout << -1 << '\n';
        return;
    }
    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