Submission #750383

#	Time	Username	Problem	Language	Result	Execution time	Memory
750383		MuntherCarrot	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	50 / 100	374 ms	102400 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define F first
#define S second
#define pb push_back
#define all(a) a.begin(),a.end()
const int N=1e6+500;
const int off=(1<<18);
const int MOD = 1e9+7;

vector<vector<int>>gr(N);
int val[N],vis[N];
map<pair<int,int>,int>mp;
void dij(int a){
   // vis[a]=1;
   // val[a]=0;
   priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
   pq.push({0,a});
   while(!pq.empty()){
      int vl=pq.top().F,x=pq.top().S;
      pq.pop();
      if(vis[x])continue;
      vis[x]=1;
      val[x] = vl;
      // cout<<vl<<' '<<x<<endl;
      for(auto it:gr[x]){
         pq.push({mp[{x, it}] + vl,it});
      }
   }
}
signed main(){
   ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
   int n,m;
   cin >> m >> n;
   char ch[m][n];
   for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
         cin >> ch[i][j];
      }
   }
   for(int i=0;i<m;i++){
      for(int j=0;j<n;j++){
         val[n*i+j]=INT_MAX;
         if(ch[i][j]=='X'){
            // vis[n*i+j]=1;
            continue;
         }
         if(i){
            gr[n*i+j].pb(n*(i-1)+j);
            if(ch[i][j]=='E')mp[{n*i+j,n*(i-1)+j}]=3;
            if(ch[i][j]=='W')mp[{n*i+j,n*(i-1)+j}]=1;
            if(ch[i][j]=='N')mp[{n*i+j,n*(i-1)+j}]=0;
            if(ch[i][j]=='S')mp[{n*i+j,n*(i-1)+j}]=2;
         }
         if(i<m-1){
            gr[n*i+j].pb(n*(i+1)+j);
            if(ch[i][j]=='E')mp[{n*i+j,n*(i+1)+j}]=1;
            if(ch[i][j]=='W')mp[{n*i+j,n*(i+1)+j}]=3;
            if(ch[i][j]=='N')mp[{n*i+j,n*(i+1)+j}]=2;
            if(ch[i][j]=='S')mp[{n*i+j,n*(i+1)+j}]=0;
         }
         if(j){
            gr[n*i+j].pb(n*i+j-1);
            if(ch[i][j]=='E')mp[{n*i+j,n*i+j-1}]=2;
            if(ch[i][j]=='W')mp[{n*i+j,n*i+j-1}]=0;
            if(ch[i][j]=='N')mp[{n*i+j,n*i+j-1}]=3;
            if(ch[i][j]=='S')mp[{n*i+j,n*i+j-1}]=1;
         }
         if(j<n-1){
            gr[n*i+j].pb(n*i+j+1);
            if(ch[i][j]=='E')mp[{n*i+j,n*i+j+1}]=0;
            if(ch[i][j]=='W')mp[{n*i+j,n*i+j+1}]=2;
            if(ch[i][j]=='N')mp[{n*i+j,n*i+j+1}]=1;
            if(ch[i][j]=='S')mp[{n*i+j,n*i+j+1}]=3;
         }
      }
   }
   dij(0);
   int lst=(n)*(m)-1;
   // for(int i=0;i<m;i++){
   //     for(int j=0;j<n;j++)
   //      cout << val[i * n + j] << ' ';
   //  cout << endl;
   // }
   if(val[lst]==INT_MAX)val[lst]=-1;
   cout<<val[lst];

}

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