oj.uz

Submission #226623

# Submission time Handle Problem Language Result Execution time Memory
226623 2020-04-24T14:48:29 Z Theo830 Awesome Arrowland Adventure (eJOI19_adventure) C++17
12 / 100
 9 ms 6272 KB 
        #include <bits/stdc++.h>
        using namespace std;
        typedef long long ll;
        ll INF = 1e18+7;
        typedef pair<ll,ll> ii;
        #define iii pair<ii,ll>
        #define f(i,a,b) for(long long i = a;i < b;i++)
        #define rf(i,a,b) for(long long i=a;i>=b;i--)
        #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
        #define w(t) while(t--)
        #define c(n); cin>>n;
        #define p(n) cout<<n;
        #define pl(n) cout<<n<<"\n";
        #define ps(n); cout<<n<<" ";
        #define F first
        #define S second
        #define pb(a) push_back(a)
        #define all(x) (x).begin(), (x).end()
        #define ull unsigned long long
        #define vll vector<ll>
        #define vii vector<ii>
        #define mkp make_pair
        #define ld long double
        #define arrin(a,n) f(i,0,n){cin>>a[i];}
        #define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
        #define prllclock cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
        #define PI (2LL*acos(0))
        vll visit,taken;
        ll dist[500 * 500 + 5];
        vector<vll> adj;
        vii adj2LL[500 * 500 + 5];
        priority_queue<ii,vector<ii>, greater<ii> > pq;
        void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2LL[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
        int main(void){
            fastio;
            ll n,m;
            c(n);
            c(m);
            char arr[n][m];
            f(i,0,n){
                f(j,0,m){
                    c(arr[i][j]);
                }
            }
            f(i,0,n){
                f(j,0,m){
                    if(arr[i][j] == 'N'){
                        if(i-1 >= 0)
                        adj2LL[j*m+i].pb(ii(j*m+i-1,0));
                        if(j+1 <= m-1)
                        adj2LL[j*m+i].pb(ii((j+1)*m+i,1));
                        if(i+1 <= n-1)
                        adj2LL[j*m+i].pb(ii(j*m+i+1,2));
                        if(j-1 >= 0)
                        adj2LL[j*m+i].pb(ii((j-1) *m + i,3));
                    }
                    else if(arr[i][j] == 'E'){
                        if(i-1 >= 0)
                        adj2LL[j*m+i].pb(ii(j*m+i-1,3));
                        if(j+1 <= m-1)
                        adj2LL[j*m+i].pb(ii((j+1)*m+i,0));
                        if(i+1 <= n-1)
                        adj2LL[j*m+i].pb(ii(j*m+i+1,1));
                        if(j-1 >= 0)
                        adj2LL[j*m+i].pb(ii((j-1) *m + i,2));
                    }
                    else if(arr[i][j] == 'S'){
                        if(i-1 >= 0)
                        adj2LL[j*m+i].pb(ii(j*m+i-1,2));
                        if(j+1 <= m-1)
                        adj2LL[j*m+i].pb(ii((j+1)*m+i,3));
                        if(i+1 <= n-1)
                        adj2LL[j*m+i].pb(ii(j*m+i+1,0));
                        if(j-1 >= 0)
                        adj2LL[j*m+i].pb(ii((j-1) *m + i,1));
                    }
                    else if(arr[i][j] == 'W'){
                        if(i-1 >= 0)
                        adj2LL[j*m+i].pb(ii(j*m+i-1,1));
                        if(j+1 <= m-1)
                        adj2LL[j*m+i].pb(ii((j+1)*m+i,2));
                        if(i+1 <= n-1)
                        adj2LL[j*m+i].pb(ii(j*m+i+1,3));
                        if(j-1 >= 0)
                        adj2LL[j*m+i].pb(ii((j-1) *m + i,0));
                    }
                }
            }
            f(i,0,n*m+5){
                dist[i] = INF;
            }
            dijkstra(0);
            ll i = n-1;
            ll j = m-1;
            if(dist[j*m + i] >= INF){
                pl(-1);
                return 0;
            }
            pl(dist[j*m + i]);
        }

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6144 KB Output is correct
2 Correct 8 ms 6144 KB Output is correct
3 Correct 8 ms 6144 KB Output is correct
4 Correct 8 ms 6272 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 6272 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6272 KB Output isn't correct
2 Halted 0 ms 0 KB -