Submission #447294

#	Time	Username	Problem	Language	Result	Execution time	Memory
447294		Agnimandur	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	122 ms	24320 KiB

adventure

#include <bits/stdc++.h>
 
#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define vl vector<long long>
#define pii pair<int, int>
#define pll pair<ll,ll>
#define add push_back
#define REP(i,a) for (int i = 0; i < (a); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;
 
const int INF = 1005000000; 
//const ll MOD = 1000000007LL;
const ll MOD = 998244353LL;
 
 
 
int ni() {
    int x; cin >> x;
    return x;
}
 
ll nl() {
    ll x; cin >> x;
    return x;
}
 
double nd() {
    double x; cin >> x;
    return x;
}
 
string next() {
    string x; cin >> x;
    return x;
}


struct Dijkstra {
    vector<vector<pii>> graph;
    int N;

    Dijkstra(int N) {
        graph.assign(N,vector<pii>{});
        this->N=N;
    }

    void addEdge(int u, int v, int w) {
        graph[u].add(make_pair(v,w));
    }

    vl dijkstra(int root) {
        ll INF = 1000000000000000000LL;
        vl dists(N);
        dists.assign(N, INF);

        dists[root] = 0LL;
        minpq<pair<ll,int>> q;
        q.push({0LL, root});

        while (!q.empty()) {
            int v = q.top().second;
            ll d_v = q.top().first;
            q.pop();

            for (auto edge : graph[v]) {
                int to = edge.first;
                ll len = edge.second;

                if (d_v + len < dists[to]) {
                    dists[to] = d_v + len;
                    q.push({dists[to], to});
                }
            }
        }

        return dists;
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N = ni();
    int M = ni();
    Dijkstra graph(N*M);
    string dir = "NESW";
    vvi dirs = {{-1,0},{0,1},{1,0},{0,-1}};
    REP(i,N) {
        string row = next();
        REP(j,M) {
            string c = row.substr(j,1);
            if (c=="X") continue;

            int x = i*M+j;
            int p = dir.find(c);
            REP(d,4) {
                int e = (d+p)%4;
                int newI = i+dirs[e][0];
                int newJ = j+dirs[e][1];
                if (newI >= 0 && newI < N && newJ >= 0 && newJ < M) {
                    int y = newI*M+newJ;
                    graph.addEdge(x,y,d);
                }
            }
        }
    }

    vl dists = graph.dijkstra(0);
    ll ans = dists[N*M-1];
    if (ans > 2000) ans = -1;
    cout << ans;
}

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