oj.uz

Submission #427271

# Submission time Handle Problem Language Result Execution time Memory
427271 2021-06-14T13:52:26 Z model_code Robot Race (CPSPC17_race) C++
20 / 100
 3000 ms 6164 KB 
#include <cassert>
#include <iostream>
#include <queue>
#include <string>
#include <utility>

using namespace std;

const int MAXN = 1000;

const int dr[2] = { 0, 1 };
const int dc[2] = { 1, 0 };

int n, m, q;
bool empty[MAXN][MAXN];
int age[MAXN][MAXN];
int now;

bool path_exists(int sr, int sc, int tr, int tc) {
	if (sr == tr && sc == tc) return true;
	now++;
	queue<pair<int, int>> q;
	q.emplace(sr, sc);
	age[sr][sc] = now;
	while (!q.empty()) {
		int r = q.front().first;
		int c = q.front().second;
		q.pop();
		if (r == tr && c == tc) break;
		for (int i = 0; i < 2; i++) {
			int nr = r + dr[i];
			int nc = c + dc[i];
			if (nr < n && nc < m && empty[nr][nc] && age[nr][nc] != now) {
				q.emplace(nr, nc);
				age[nr][nc] = now;
			}
		}
	}
	return age[tr][tc] == now;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	assert(n >= 1 && n <= 1000);
	assert(m >= 1 && m <= 1000);
	assert(q >= 1 && q <= 1000000);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		assert((int) s.length() == m);
		for (int j = 0; j < m; j++) {
			empty[i][j] = s[j] == '.';
		}
	}
	for (int i = 0; i < q; i++) {
		int sr, sc, tr, tc;
		cin >> sr >> sc >> tr >> tc;
		assert(sr >= 1 && sr <= n);
		assert(sc >= 1 && sc <= m);
		assert(tr >= 1 && tr <= n);
		assert(tc >= 1 && tc <= m);
		sr--; sc--; tr--; tc--;
		assert(empty[sr][sc]);
		assert(empty[tr][tc]);
		bool ans = path_exists(sr, sc, tr, tc);
		printf("%s\n", ans ? "YES" : "NO");
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 5196 KB Output is correct
2 Correct 585 ms 5136 KB Output is correct
3 Correct 23 ms 5068 KB Output is correct
4 Correct 5 ms 3788 KB Output is correct
5 Correct 4 ms 2380 KB Output is correct
6 Correct 5 ms 2380 KB Output is correct
7 Correct 556 ms 5960 KB Output is correct
8 Correct 642 ms 5904 KB Output is correct
9 Correct 622 ms 6080 KB Output is correct
10 Correct 608 ms 6008 KB Output is correct
11 Correct 119 ms 5956 KB Output is correct
12 Correct 58 ms 5848 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 683 ms 5196 KB Output is correct
2 Correct 585 ms 5136 KB Output is correct
3 Correct 23 ms 5068 KB Output is correct
4 Correct 5 ms 3788 KB Output is correct
5 Correct 4 ms 2380 KB Output is correct
6 Correct 5 ms 2380 KB Output is correct
7 Correct 556 ms 5960 KB Output is correct
8 Correct 642 ms 5904 KB Output is correct
9 Correct 622 ms 6080 KB Output is correct
10 Correct 608 ms 6008 KB Output is correct
11 Correct 119 ms 5956 KB Output is correct
12 Correct 58 ms 5848 KB Output is correct
13 Execution timed out 3070 ms 6164 KB Time limit exceeded
14 Halted 0 ms 0 KB -