oj.uz

Submission #1026522

# Submission time Handle Problem Language Result Execution time Memory
1026522 2024-07-18T07:30:25 Z LM1 Awesome Arrowland Adventure (eJOI19_adventure) C++14
100 / 100
 132 ms 5216 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
//#define int long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const int N=555;
char a[N][N];
int n,m,d[N][N];
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
//c1 aris
//c2 gvinda
int rot(int x2,int y2,int m1,int m2){
	char c1=a[x2][y2];
	char c2;
	if(m1==1)c2='S';
	if(m2==1)c2='E';
	if(m1==-1)c2='N';
	if(m2==-1)c2='W';
	if(c1==c2)return 0;
	string c3="";c3+=c1;c3+=c2;
	//cout<<c3<<" ";
	if(c3=="NE" or c3=="ES" or c3=="SW" or c3=="WN")return 1;
	if(c3=="NS" or c3=="EW" or c3=="SN" or c3=="WE")return 2;
	if(c3=="NW" or c3=="EN" or c3=="SE" or c3=="WS")return 3;
}
void dijkstra(){
	d[0][0]=0;
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>pq;
	pq.push({0,{0,0}});
	while(pq.size()){
		auto st=pq.top();
		pq.pop();
		int x=st.ss.ff;
		int y=st.ss.ss;
		int d1=st.ff;
		if(a[x][y]=='X')continue;
		for(int i=0;i<4;i++){
			int xn=x+xx[i];
			int yn=y+yy[i];
			if(xn<0 or xn>n-1)continue;
			if(yn<0 or yn>m-1)continue;
			int r=rot(x,y,xx[i],yy[i]);
			if(d1+r<d[xn][yn]){
				d[xn][yn]=d1+r;
				pq.push({d[xn][yn],{xn,yn}});
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			d[i][j]=1e9;
			cin>>a[i][j];
		}
	}
	//cout<<rot(0,0,0,1);
	dijkstra();
//	for(int i=0;i<n;i++){
//		for(int j=0;j<m;j++){
//			cout<<d[i][j]<<" ";
//		}cout<<endl;
//	}
	if(d[n-1][m-1]==1e9)cout<<-1;
	else cout<<d[n-1][m-1];
}

Compilation message

adventure.cpp: In function 'int rot(int, int, int, int)':
adventure.cpp:24:12: warning: control reaches end of non-void function [-Wreturn-type]
   24 |  string c3="";c3+=c1;c3+=c2;
      |            ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 460 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 464 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 456 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 1 ms 348 KB Output is correct
34 Correct 0 ms 464 KB Output is correct
35 Correct 6 ms 604 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 7 ms 604 KB Output is correct
38 Correct 1 ms 1116 KB Output is correct
39 Correct 73 ms 1884 KB Output is correct
40 Correct 81 ms 1884 KB Output is correct
41 Correct 3 ms 1884 KB Output is correct
42 Correct 83 ms 2084 KB Output is correct
43 Correct 132 ms 5216 KB Output is correct
44 Correct 3 ms 1884 KB Output is correct