Submission #782155

#	Time	Username	Problem	Language	Result	Execution time	Memory
782155		HoriaHaivas	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	86 ms	21568 KiB

adventure

/*
    "TLE is like the wind, always by my side"
    - Yasuo - 2022 -
*/
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")

using namespace std;

struct edge
{
    int endnode;
    int cost;
};

struct pqnode
{
    int node;
    int cost;
};

struct cmp
{
    bool operator()(pqnode a, pqnode b)
    {
         return a.cost>b.cost;
    }
};

int n,m;
char a[501][501];
int mincost[250001];
vector<edge> nodes[250001];
bool visited[250001];
priority_queue<pqnode,vector<pqnode>,cmp> pq;
const int inf = 1e9;

int compress(int l, int c)
{
    return m*(l-1)+c;
}

void dijkstra(int source)
{
     int i,c,currnode;
     for (i=1;i<=n*m;i++)
     {
          mincost[i]=inf;
     }
     pq.push({source,0});
     while (!pq.empty())
     {
          currnode=pq.top().node;
          c=pq.top().cost;
          pq.pop();
          if (!visited[currnode])
          {
              visited[currnode]=1;
              mincost[currnode]=c;
              for (i=0;i<nodes[currnode].size();i++)
              {
                   if (!visited[nodes[currnode][i].endnode] && c+nodes[currnode][i].cost<mincost[nodes[currnode][i].endnode])
                   pq.push({nodes[currnode][i].endnode,c+nodes[currnode][i].cost});
              }
          }
     }
}

void addedge(int node, int l, int c, char dir)
{
      if (dir=='N')
      {
          if (l-1>0 && l-1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l-1,c),0});
          if (l+1>0 && l+1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l+1,c),2});
          if (l>0 && l<n+1 && c-1>0 && c-1<m+1)
          nodes[node].push_back({compress(l,c-1),3});
          if (l>0 && l<n+1 && c+1>0 && c+1<m+1)
          nodes[node].push_back({compress(l,c+1),1});
      }
      if (dir=='W')
      {
          if (l-1>0 && l-1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l-1,c),1});
          if (l+1>0 && l+1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l+1,c),3});
          if (l>0 && l<n+1 && c-1>0 && c-1<m+1)
          nodes[node].push_back({compress(l,c-1),0});
          if (l>0 && l<n+1 && c+1>0 && c+1<m+1)
          nodes[node].push_back({compress(l,c+1),2});
      }
      if (dir=='S')
      {
          if (l-1>0 && l-1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l-1,c),2});
          if (l+1>0 && l+1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l+1,c),0});
          if (l>0 && l<n+1 && c-1>0 && c-1<m+1)
          nodes[node].push_back({compress(l,c-1),1});
          if (l>0 && l<n+1 && c+1>0 && c+1<m+1)
          nodes[node].push_back({compress(l,c+1),3});
      }
      if (dir=='E')
      {
          if (l-1>0 && l-1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l-1,c),3});
          if (l+1>0 && l+1<n+1 && c>0 && c<m+1)
          nodes[node].push_back({compress(l+1,c),1});
          if (l>0 && l<n+1 && c-1>0 && c-1<m+1)
          nodes[node].push_back({compress(l,c-1),2});
          if (l>0 && l<n+1 && c+1>0 && c+1<m+1)
          nodes[node].push_back({compress(l,c+1),0});
      }
}

int main()
{
    ifstream fin("secvp.in");
    ofstream fout("secvp.out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int i,j;
    cin >> n >> m;
    for (i=1;i<=n;i++)
    {
         for (j=1;j<=m;j++)
         {
              cin >> a[i][j];
         }
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
             if (a[i][j]!='X')
             addedge(compress(i,j),i,j,a[i][j]);
        }
    }
    dijkstra(1);
    if (mincost[n*m]!=inf)
    cout << mincost[n*m];
    else
    cout << -1;
}

Compilation message (stderr)

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

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