oj.uz

Submission #260126

# Submission time Handle Problem Language Result Execution time Memory
260126 2020-08-09T11:03:21 Z tomsyd Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 165 ms 9060 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

vector<pair<int,int>> dir = {{1,0},{0,1},{-1,0},{0,-1}};
vector<char> d = {'S','E','N','W'};
const int inf = LLONG_MAX/2;

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m;
	cin >> n >> m;
	map<char,map<char,int>> dist;
	dist['N']['S'] = 2;
	dist['S']['N'] = 2;
	dist['E']['W'] = 2;
	dist['W']['E'] = 2;
	dist['W']['S'] = 3;
	dist['N']['W'] = 3;
	dist['E']['N'] = 3;
	dist['S']['E'] = 3;
	for (auto i:d){
		for (auto j:d){
			if (i == j) dist[i][j] = 0;
			else if (!dist[i].count(j)) dist[i][j] = 1;
		}
	}
	/*for (auto i:dist){
		for (auto j:i.second){
			cout << i.first << ' ' << j.first << ' ' << j.second << '\n';
		}
	}*/
	vector<string> v(n);
	for (int i=0; i<n; ++i) cin >> v[i];
	if (v[0][0] == 'X'){
		if (n == 1 and m == 1) cout << 0;
		else cout << -1;
		return 0;
	}
	vector<vector<int>> vu(n,vector<int>(m,inf));
	priority_queue<tuple<int,int,int>,vector<tuple<int,int,int>>,greater<tuple<int,int,int>>> q;
	q.emplace(0,0,0);
	vu[0][0] = 0;
	while (!q.empty()){
		auto f = q.top();
		int x,y,a;
		tie(a,x,y) = f;
		q.pop();
		for (int i=0; i<4; ++i){
			int nx = dir[i].first + x, ny = dir[i].second + y;
			a += dist[v[x][y]][d[i]];
			if (nx >= 0 and ny >= 0 and nx < n and ny < m and vu[nx][ny] > a){
				vu[nx][ny] = a;
				if (v[nx][ny] != 'X') q.emplace(a,nx,ny);
			}
			a -= dist[v[x][y]][d[i]];
		}
	}
	if (vu[n-1][m-1] == inf) cout << -1;
	else cout << vu[n-1][m-1];
	return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 512 KB Output is correct
18 Correct 1 ms 288 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 0 ms 384 KB Output is correct
28 Correct 0 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 0 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 6 ms 512 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 7 ms 640 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 65 ms 2936 KB Output is correct
40 Correct 64 ms 2940 KB Output is correct
41 Correct 3 ms 2816 KB Output is correct
42 Correct 68 ms 2936 KB Output is correct
43 Correct 165 ms 9060 KB Output is correct
44 Correct 2 ms 896 KB Output is correct