oj.uz

Submission #773956

# Submission time Handle Problem Language Result Execution time Memory
773956 2023-07-05T09:57:31 Z Dzadzo Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 72 ms 8980 KB 
#include <bits/stdc++.h>
#define ll long long
#define int ll
#define pb push_back
#define S second
#define F first
#define pii pair<int,int>
#define vi vector <int>
#define vvi vector <vector<int>>
#define INF LLONG_MAX
#define MOD 1000000009
#define MAXN 100000
using namespace std;
int kx[4]={1,-1,0,0};
int ky[4]={0,0,1,-1};
main() {
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	int n,m;
	cin>>n>>m;
	vector <vector < char >> d(n+1,vector <char> (m+1));
	int dist[n+1][m+1];
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>d[i][j];
			if (d[i][j]=='N')d[i][j]='u';
			if (d[i][j]=='S')d[i][j]='d';
			if (d[i][j]=='E')d[i][j]='r';
			if (d[i][j]=='W')d[i][j]='l';
			dist[i][j]=INF;
		}
	}
	priority_queue <pair <int,pii>> q;
	dist[1][1]=0;
	q.push({0,{1,1}});
	while (!q.empty()){
		pair <int,pii> p=q.top();
		q.pop();
		int x=p.S.F;
		int y=p.S.S;
		int val[4];
		if (d[x][y]=='X')continue;
		if (d[x][y]=='d'){
			val[0]=0;
			val[1]=2;
			val[2]=3;
			val[3]=1;
		}
		if (d[x][y]=='u'){
			val[0]=2;
			val[1]=0;
			val[2]=1;
			val[3]=3;
		}
		if (d[x][y]=='r'){
			val[0]=1;
			val[1]=3;
			val[2]=0;
			val[3]=2;
		}
		if (d[x][y]=='l'){
			val[0]=3;
			val[1]=1;
			val[2]=2;
			val[3]=0;
		}		
		for (int i=0;i<4;i++){
			int curx=x+kx[i];
			int cury=y+ky[i];
			if (curx==0 || cury==0 || curx==n+1 || cury==m+1)continue;
			if (dist[curx][cury]>dist[x][y]+val[i]){
				dist[curx][cury]=dist[x][y]+val[i];
				q.push({-dist[curx][cury],{curx,cury}});
			}
			
		}
	}
	if (dist[n][m]==INF)cout<<-1;else
	cout<<dist[n][m];
}

Compilation message

adventure.cpp:16:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   16 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 312 KB Output is correct
4 Correct 1 ms 324 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 0 ms 320 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 0 ms 320 KB Output is correct
20 Correct 0 ms 288 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 0 ms 212 KB Output is correct
23 Correct 0 ms 312 KB Output is correct
24 Correct 1 ms 324 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 0 ms 312 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 0 ms 212 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct
33 Correct 0 ms 320 KB Output is correct
34 Correct 1 ms 212 KB Output is correct
35 Correct 4 ms 460 KB Output is correct
36 Correct 1 ms 320 KB Output is correct
37 Correct 5 ms 608 KB Output is correct
38 Correct 1 ms 724 KB Output is correct
39 Correct 47 ms 2780 KB Output is correct
40 Correct 48 ms 2844 KB Output is correct
41 Correct 7 ms 2772 KB Output is correct
42 Correct 49 ms 2852 KB Output is correct
43 Correct 72 ms 8980 KB Output is correct
44 Correct 7 ms 2768 KB Output is correct