oj.uz

Submission #467240

# Submission time Handle Problem Language Result Execution time Memory
467240 2021-08-22T08:14:53 Z Stickfish Awesome Arrowland Adventure (eJOI19_adventure) C++17
34 / 100
 1 ms 292 KB 
#include <iostream>
#include <complex>
#include <set>
using namespace std;

const complex<int> IMAG(0, 1);
const int MAXN = 101;
const int INF = 1e9;
complex<int> f[MAXN][MAXN];
int dp[MAXN][MAXN];

bool operator<(const complex<int>& c1, const complex<int>& c2){
	return c1.real() < c2.real() || c1.real() == c2.real() && c1.imag() < c2.imag();
}

struct ccomporator{
	bool operator()(const pair<int, complex<int>> p1, const pair<int, complex<int>> p2) const {
		if(p1.first < p2.first)
			return true;
		if(p1.first > p2.first)
			return false;
		if(p1.second.real() < p2.second.real())
			return true;
		if(p1.second.real() > p2.second.real())
			return false;
		if(p1.second.imag() < p2.second.imag())
			return true;
		return false;

	}
};


signed main(){
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; ++i){
		for(int j = 0; j < m; ++j){
			char c;
			cin >> c;
			if(c == 'E'){
				f[i][j] = IMAG;
			} else if(c == 'N'){
				f[i][j] = -1;
			} else if(c == 'S'){
				f[i][j] = 1;
			} else if(c == 'W'){
				f[i][j] = -IMAG;
			} else {
				f[i][j] = 0;
			}
			dp[i][j] = INF;
		}
	}
	dp[0][0] = 0;
	set<pair<int, complex<int>>, ccomporator> st;
	st.insert({0, 0});
	while(st.size()){
		complex<int> pt = st.begin()->second;
		st.erase(st.begin());
		for(complex<int> timer = 0, mv = f[pt.real()][pt.imag()]; timer != 4; timer += 1, mv *= -IMAG){
			complex<int> npt = pt + mv;
			if(0 <= npt.real() && npt.real() < n && 0 <= npt.imag() && npt.imag() < m && dp[npt.real()][npt.imag()] > dp[pt.real()][pt.imag()]){
				st.erase({dp[npt.real()][npt.imag()], npt});
				dp[npt.real()][npt.imag()] = min(dp[npt.real()][npt.imag()], dp[pt.real()][pt.imag()] + timer.real());
				st.insert({dp[npt.real()][npt.imag()], npt});
			}
		}
	}
	if(dp[n - 1][m - 1] == INF){
		cout << -1 << endl;
	} else {
		cout << dp[n - 1][m - 1] << endl;
	}
}

Compilation message

adventure.cpp: In function 'bool operator<(const std::complex<int>&, const std::complex<int>&)':
adventure.cpp:13:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   13 |  return c1.real() < c2.real() || c1.real() == c2.real() && c1.imag() < c2.imag();
      |                                  ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.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
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 0 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 292 KB Output is correct

Subtask #2
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
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 0 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 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 204 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 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 50.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
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 0 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 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 204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct
22 Correct 0 ms 204 KB Output is correct
23 Correct 0 ms 204 KB Output is correct
24 Correct 0 ms 204 KB Output is correct
25 Correct 1 ms 292 KB Output is correct
26 Correct 1 ms 204 KB Output is correct
27 Incorrect 1 ms 204 KB Output isn't correct
28 Halted 0 ms 0 KB -