oj.uz

Submission #441864

# Submission time Handle Problem Language Result Execution time Memory
441864 2021-07-06T11:47:26 Z nots0fast Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 110 ms 9048 KB 
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision
#define ss second
#define fori(v) for(ll i=0; i<v; i++)
#define forj(v) for(ll j=0; j<v; j++)
#define fork(v) for(ll k=0; k<v; k++)
#define forl(v) for(ll l=0; l<v; l++)
#define fort(v) for(ll t=0; t<v; t++)
#define forz(v) for(ll z=0; z<v; z++)
#define forx(v) for(ll x=0; x<v; x++)
#define fory(v) for(ll y=0; y<v; y++)
#define ll long long
#define ld long double
#define pb(a) push_back(a)
#define mt make_tuple
#define MAX (int)(2*pow(10,6) + 5)
// #define cout out
// #define cin in
ll inf = pow(10, 18) + 100;
ll INF = pow(10, 9);
ll modulo = pow(10, 9) + 7;
double eps = 1e-10;

// start time 14 : 42

ll dx[4] = {-1, 0, 1, 0};
ll dy[4] = {0,  1, 0,-1};
string dir = "NESW";

void deal(){
	ll n, m;
	cin>>n>>m;
	vector<vector<char> > arr(n, vector<char>(m));
	fori(n){
		forj(m){
			cin>>arr[i][j];
		}
	}
	vector<vector<ll> > dt(n, vector<ll>(m, inf));
	dt[0][0] = 0;
	priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll> >, greater<tuple<ll,ll,ll> > > pq;
	pq.push(mt(0,0,0));
	while(!pq.empty()){
		auto [val, x, y] = pq.top();
		pq.pop();
		if(dt[x][y]!=val){
			continue;
		}
		if(arr[x][y] == 'X'){
			continue;
		}
		ll wh = dir.find(arr[x][y]);
		fork(4){
			ll x1 = x+dx[k], y1 = y + dy[k];
			if(x1 > -1 && y1 > -1 && x1 < n && y1 < m){
				ll add = (k-wh+4)%4;
				if(dt[x][y] + add < dt[x1][y1]){
					dt[x1][y1] = dt[x][y] + add;
					pq.push(mt(dt[x1][y1], x1, y1));
				}
			}
		}
	}
	if(dt[n-1][m-1] == inf){
		dt[n-1][m-1] = -1;
	}
	cout<<dt[n-1][m-1];
}


int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	deal();  
}

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 0 ms 204 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 312 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 1 ms 204 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 0 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 312 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 1 ms 204 KB Output is correct
24 Correct 1 ms 204 KB Output is correct
25 Correct 0 ms 204 KB Output is correct
26 Correct 0 ms 204 KB Output is correct
27 Correct 1 ms 204 KB Output is correct
28 Correct 1 ms 204 KB Output is correct
29 Correct 1 ms 204 KB Output is correct
30 Correct 1 ms 204 KB Output is correct
31 Correct 1 ms 204 KB Output is correct
32 Correct 0 ms 204 KB Output is correct
33 Correct 1 ms 312 KB Output is correct
34 Correct 1 ms 204 KB Output is correct
35 Correct 5 ms 460 KB Output is correct
36 Correct 1 ms 332 KB Output is correct
37 Correct 6 ms 588 KB Output is correct
38 Correct 1 ms 716 KB Output is correct
39 Correct 61 ms 2844 KB Output is correct
40 Correct 60 ms 2860 KB Output is correct
41 Correct 6 ms 2764 KB Output is correct
42 Correct 67 ms 2824 KB Output is correct
43 Correct 110 ms 9048 KB Output is correct
44 Correct 5 ms 2740 KB Output is correct