oj.uz

Submission #637375

# Submission time Handle Problem Language Result Execution time Memory
637375 2022-09-01T14:18:24 Z VitaliyFS Awesome Arrowland Adventure (eJOI19_adventure) C++17
100 / 100
 85 ms 11016 KB 
#include<bits/stdc++.h>

using namespace std;

#define fr first
#define sc second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

const ll INF = 1000000000000000007, DIM = 1007, DIM2 = 107, MAXN = 100007, MOD = 1000000007;

ll tt, mid, res,f, a[DIM], b[DIM], d[DIM][DIM], dist[DIM][DIM], used[DIM],  dp[DIM], y, type, ptr, root, cnt, sum, pos, h, p, sx,sy, id, testcase, curans, nn, split, n, m, x, k1, k2, changecnt,k,l,r,v,u, l1,r1,l2,r2;
bool flag, flag2;
char c;
string s[DIM];
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> q;

void check(ll x, ll y, ll x2, ll y2, char ch) {
	if(x2<1||x2>n||y2<1||y2>m)return;
	if(dist[x][y] + d[s[x][y]][ch] < dist[x2][y2]){
		dist[x2][y2]=dist[x][y] + d[s[x][y]][ch];
		q.push({dist[x2][y2], {x2,y2}});
	}
}

void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];s[i]="&"+s[i];
	}
	d['N']['E']=1;
	d['N']['S']=2;
	d['N']['W']=3;
	d['E']['S']=1;
	d['E']['W']=2;
	d['E']['N']=3;
	d['S']['W']=1;
	d['S']['N']=2;
	d['S']['E']=3;
	d['W']['N']=1;
	d['W']['E']=2;
	d['W']['S']=3;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			dist[i][j] =INF;
	dist[1][1] = 0;
	q.push({0, {1,1}});
	while(!q.empty()){
		x=q.top().sc.fr; y = q.top().sc.sc;q.pop();
		if(s[x][y]=='X')continue;
		check(x,y,x+1,y,'S');
		check(x,y,x-1,y,'N');
		check(x,y,x,y+1,'E');
		check(x,y,x,y-1,'W');
	}
	if(dist[n][m]==INF){cout<<"-1\n";return;}
	cout<<dist[n][m]<<'\n';
}

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

	tt=1;
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//cin>>tt;
	while(tt--) {
		solve();
	}
	return 0;
}

Compilation message

adventure.cpp: In function 'void check(ll, ll, ll, ll, char)':
adventure.cpp:23:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |  if(dist[x][y] + d[s[x][y]][ch] < dist[x2][y2]){
      |                           ^
adventure.cpp:23:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |  if(dist[x][y] + d[s[x][y]][ch] < dist[x2][y2]){
      |                             ^~
adventure.cpp:24:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |   dist[x2][y2]=dist[x][y] + d[s[x][y]][ch];
      |                                      ^
adventure.cpp:24:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |   dist[x2][y2]=dist[x][y] + d[s[x][y]][ch];
      |                                        ^~

Subtask #1
10.0 / 10.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
16.0 / 16.0

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

Subtask #5
50.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 360 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 1 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 1 ms 340 KB Output is correct
30 Correct 1 ms 340 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 5 ms 724 KB Output is correct
36 Correct 0 ms 356 KB Output is correct
37 Correct 5 ms 980 KB Output is correct
38 Correct 1 ms 1780 KB Output is correct
39 Correct 48 ms 4868 KB Output is correct
40 Correct 49 ms 4820 KB Output is correct
41 Correct 4 ms 4828 KB Output is correct
42 Correct 53 ms 4896 KB Output is correct
43 Correct 85 ms 11016 KB Output is correct
44 Correct 3 ms 4820 KB Output is correct