oj.uz

Submission #525679

# Submission time Handle Problem Language Result Execution time Memory
525679 2022-02-12T13:53:40 Z ammar2000 Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 82 ms 11036 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define F first
#define S second
#define coy cout<<"YES\n"
#define con cout<<"NO\n"
#define co1 cout<<"-1\n"
#define sc(x) scanf("%lld",&x)
#define all(x) x.begin(),x.end()
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int SI=3e5+7;
ll INF=8e18+7;
int dx[] = {1 , -1 , 0 , 0};
int dy[] = {0 , 0 , 1 , -1};
int MOD=1e9+7;
ll n,m ,vis[555][555],ans[555][555];
map <char,ll> mp[4];
char c[555][555];
priority_queue< pair<ll,pair < ll,ll> > > pq;
int main()
{
   fast
   mp[0]['N']=0,mp[1]['N']=1, mp[2]['N']=2,mp[3]['N']=3;
   mp[0]['E']=3,mp[1]['E']=0, mp[2]['E']=1,mp[3]['E']=2;
   mp[0]['S']=2,mp[1]['S']=3, mp[2]['S']=0,mp[3]['S']=1;
   mp[0]['W']=1,mp[1]['W']=2, mp[2]['W']=3,mp[3]['W']=0;
   cin>>m>>n;
   for (int i=0;i<m;i++)
    for (int u=0;u<n;u++)
      cin>>c[i][u];
   for (int i=0;i<=m;i++)
    for (int u=0;u<=n;u++)
       ans[i][u]=-INF;
   ans[0][0]=0;
   pq.push({0,{0,0}});
   while (pq.size())
   {
       ll d=pq.top().F,x=pq.top().S.F,y=pq.top().S.S;
       pq.pop();
       if (vis[x][y]||c[x][y]=='X')
        continue;
        vis[x][y]=1;
       if (x>0&&ans[x-1][y]<d-mp[0][c[x][y]])
       ans[x-1][y]=d-mp[0][c[x][y]],pq.push({ans[x-1][y],{x-1,y}});
       if (y>0&&ans[x][y-1]<d-mp[3][c[x][y]])
       ans[x][y-1]=d-mp[3][c[x][y]],pq.push({ans[x][y-1],{x,y-1}});
       if (x<m-1&&ans[x+1][y]<d-mp[2][c[x][y]])
       ans[x+1][y]=d-mp[2][c[x][y]],pq.push({ans[x+1][y],{x+1,y}});
       if (y<n-1&&ans[x][y+1]<d-mp[1][c[x][y]])
        ans[x][y+1]=d-mp[1][c[x][y]],pq.push({ans[x][y+1],{x,y+1}});
   }
   if (ans[m-1][n-1]==-INF)
    co1;
   else cout <<-ans[m-1][n-1];
   // use scanf not cin
   return 0;
}

Compilation message

adventure.cpp: In function 'int main()':
adventure.cpp:42:8: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   42 |        if (vis[x][y]||c[x][y]=='X')
      |        ^~
adventure.cpp:44:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   44 |         vis[x][y]=1;
      |         ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 1 ms 332 KB Output is correct

Subtask #4
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 324 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 328 KB Output is correct

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 0 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 332 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 328 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 0 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 1 ms 332 KB Output is correct
30 Correct 1 ms 324 KB Output is correct
31 Correct 0 ms 332 KB Output is correct
32 Correct 1 ms 332 KB Output is correct
33 Correct 1 ms 332 KB Output is correct
34 Correct 1 ms 328 KB Output is correct
35 Correct 5 ms 860 KB Output is correct
36 Correct 0 ms 336 KB Output is correct
37 Correct 6 ms 1220 KB Output is correct
38 Correct 1 ms 1624 KB Output is correct
39 Correct 54 ms 5372 KB Output is correct
40 Correct 54 ms 5168 KB Output is correct
41 Correct 6 ms 3012 KB Output is correct
42 Correct 57 ms 5264 KB Output is correct
43 Correct 82 ms 11036 KB Output is correct
44 Correct 4 ms 3020 KB Output is correct