Submission #447293

#	Time	Username	Problem	Language	Result	Execution time	Memory
447293		Agnimandur	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	0 / 100	3 ms	592 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 LazyST {
    vl tree;
    vl lazy;
    int N;
    ll NONE;

    LazyST(int n) {
        N = n;
        NONE = 0LL;
        tree.assign(4*N+1,0LL);
        lazy.assign(4*N+1,0LL);
    }

    void add(int L, int R, ll val) {
        add(0,0,N-1,L,R,val);
    }

    void add(int n, int L, int R, int uL, int uR, ll val) {
        push(n,L,R);
        if (uL <= L && R <= uR) {
            //fully contained
            lazy[n] += val;
            push(n,L,R);
            return;
        } else if (L>uR || R<uL || L==R) {
            //not contained at all or leaf
            return;
        }
        add(2*n+1,L,(L+R)/2,uL,uR,val); 
        add(2*n+2,(L+R)/2+1,R,uL,uR,val);
        tree[n] = merge(tree[2*n+1],tree[2*n+2]);
    }

    ll query(int L, int R) {
        return query(0,0,N-1,L,R);
    }

    ll query(int n, int L, int R, int Lq, int Rq) {
        push(n,L,R);
        if (Lq <= L && R <= Rq) {
            return tree[n];
        } else if (R < Lq || Rq < L) {
            return NONE;
        } else {
            return merge(query(2*n+1,L,(L+R)/2,Lq,Rq),query(2*n+2,(L+R)/2+1,R,Lq,Rq));
        }
    }

    void push(int n, int L, int R) {
        tree[n] += operation(lazy[n],L,R);

        if (L < R) {
            lazy[2*n+1] += lazy[n];
            lazy[2*n+2] += lazy[n];
        }
        lazy[n] = 0LL;
    }

    ll merge(ll a, ll b) {
        //return Math.min(a,b); //min,NONE=INF
        //return Math.max(a,b); //max,NONE=NEG INF
        return (a+b); //sum,NONE=0
    }

    //used to process lazy updates
    ll operation(ll a, ll L, ll R) {
        //return a; //min or max
        return (R-L+1)*a; //sum
    }
};


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() {
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
#endif
    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;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:161:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  161 |     freopen("input.txt","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
adventure.cpp:162:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  162 |     freopen("output.txt","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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