답안 #637375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
637375	2022-09-01T14:18:24 Z	VitaliyFS	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	85 ms	11016 KB

adventure

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	메모리	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct

Subtask #4
16.0 / 16.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #637375

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 12.0 / 12.0

Subtask #3 12.0 / 12.0

Subtask #4 16.0 / 16.0

Subtask #5 50.0 / 50.0

Subtask #1
10.0 / 10.0

Subtask #2
12.0 / 12.0

Subtask #3
12.0 / 12.0

Subtask #4
16.0 / 16.0

Subtask #5
50.0 / 50.0