Submission #832151

#	Time	Username	Problem	Language	Result	Execution time	Memory
832151		KaleemRazaSyed	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	235 ms	40536 KiB

adventure

#include<bits/stdc++.h>

using namespace std;

int n, m;
const int MAXN = 2.5e5+10, inf = 2e9;
vector<int> G[MAXN], W[MAXN];
int dis[MAXN];

inline bool valid(int x, int y)
{
  int i = x / m, j = x % m;
  int iy = y / m, jy = y % m;
  return (i>=0 and j>=0 and i<n and j<m and (i==iy or j==jy));
}
inline int moves(char a, char b)
{
  string s = "NESW";
  int m = 0, i;
  for(i=0;i<4;i++)
    if(s[i]==a)
      break;
  while(s[(i+m)%4]!=b)
    m++;
  return m;
}

void Dij()
{
  set<pair<int,int> > s;
  dis[0] = 0;
  for(int i=0;i<n*m;i++)
    s.insert({dis[i], i});
  while(s.size())
    {
      int v = s.begin()->second;
      s.erase(s.begin());
      for(int i=0;i<G[v].size(); i++)
	{
	  int u = G[v][i], w = W[v][i];
	  if(dis[v]+w < dis[u])
	    {
	      s.erase({dis[u], u});
	      dis[u] = dis[v] + w;
	      s.insert({dis[u], u});
	    }
	  
	}
    }
}

int main()
{
  cin >> n >> m;
  for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
      {
	int num = i*m + j;
	dis[num] = inf;
	char c;
	cin >> c;
	if(c == 'X')
	  continue;
	string dir = "EWNS";
	int d[] = {1, -1, -m, m};
	for(int k=0;k<4;k++)
	  if(valid(num+d[k], num))
	    {
	      //cerr << "edge( " << num << ", " << num+d[k] << ")\n";
	      //cerr << "move( " << c << ", " << dir[k] << ") = " << moves(c, dir[k]) << endl; 
	      G[num].push_back(num + d[k]);
	      W[num].push_back(moves(c, dir[k]));
	    }
      }
  Dij();
  int l = n*m-1;
  dis[l] = (dis[l]==inf)?-1:dis[l];
  cout << dis[l] << endl;
  return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'void Dij()':
adventure.cpp:38:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |       for(int i=0;i<G[v].size(); i++)
      |                   ~^~~~~~~~~~~~

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