oj.uz

Submission #1025580

# Submission time Handle Problem Language Result Execution time Memory
1025580 2024-07-17T07:43:54 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++14
12 / 100
 3 ms 8540 KB 
#include <bits/stdc++.h>

using namespace std;
const long long MAX=250010;
vector<pair<long long,long long> > graph[MAX];
long long n,m;
char mat[501][501];
long long dist[MAX];
bool vis[MAX];
long long get(long long i, long long j)
{
    return i*m+j;
}
struct node
{
    long long idx,cost;
    node() {};
    node(long long i, long long c)
    {
        idx=i;
        cost=c;
    }
    bool operator< (const node &tmp)const
    {
        return cost>tmp.cost;
    }
};
long long dijkstra(long long si, long long sj)
{
    priority_queue<node> q;
    for(long long i=0; i<n*m; i++)
    {
        vis[i]=false;
        dist[i]=INT_MAX;
    }
    q.push(node{si,0});
    dist[si]=0;
    while(!q.empty())
    {
        auto curr=q.top();
        q.pop();
        if(vis[curr.idx])continue;
        vis[curr.idx]=true;
        if(curr.idx==sj)return dist[curr.idx];
        for(long long i=0; i<graph[curr.idx].size(); i++)
        {
            long long neighbour=graph[curr.idx][i].first;
            long long val=graph[curr.idx][i].second;
            if(dist[neighbour]>curr.cost+val)
            {
                dist[neighbour]=curr.cost+val;
                q.push(node{neighbour,dist[neighbour]});
            }
        }
    }
    return -1;
}
int main()
{
    cin>>n>>m;
    for(long long i=0; i<n; i++)
    {
        for(long long j=0; j<m; j++)
        {
            cin>>mat[i][j];
        }
    }
    for(long long i=0; i<n; i++)
    {
        for(long long j=0; j<m; j++)
        {
            if(mat[i][j]=='X')continue;
            if(i+1<n)
            {
                long long a=get(i,j);
                long long b=get(i+1,j);
                if(mat[i][j]=='S')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='E')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='N')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='W')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
            if(j+1<m)
            {

                long long a=get(i,j);
                long long b=get(i,j+1);
                if(mat[i][j]=='E')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='N')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='W')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='S')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
            if(j-1>=0)
            {
                long long a=get(i,j);
                long long b=get(i,j-1);
                if(mat[i][j]=='W')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='S')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='E')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='N')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
            if(i-1>=0)
            {
                long long a=get(i,j);
                long long b=get(i-1,j);
                if(mat[i][j]=='N')
                {
                    graph[a].push_back({b,0});
                }
                else
                {
                    if(mat[i][j]=='W')
                    {
                        graph[a].push_back({b,1});
                    }
                    else if(mat[i][j]=='S')
                    {
                        graph[a].push_back({b,2});
                    }
                    else if(mat[i][j]=='E')
                    {
                        graph[a].push_back({b,3});
                    }
                }
            }
        }
    }
    long long res=dijkstra(0,get(n-1,n-1));
    if(res==INT_MAX)res=-1;
    cout<<res<<endl;
    return 0;
}

Compilation message

adventure.cpp: In function 'long long int dijkstra(long long int, long long int)':
adventure.cpp:45:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(long long i=0; i<graph[curr.idx].size(); i++)
      |                            ~^~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

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

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8540 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 3 ms 8540 KB Output is correct
2 Correct 2 ms 8540 KB Output is correct
3 Correct 2 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct

Subtask #4
0 / 16.0

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

Subtask #5
0 / 50.0

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