oj.uz

Submission #529091

# Submission time Handle Problem Language Result Execution time Memory
529091 2022-02-22T06:07:54 Z d2k05 Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 7136 KB 
#include <bits/stdc++.h>

#define fastio ios_base :: sync_with_stdio(0), cin.tie(0);

using namespace std;
using ll = long long;

const int mxN = 1e3 + 5, mod = 1e9 + 7;

int n, m, a[mxN][mxN];
bool used[mxN][mxN];

int main() {
	fastio;
	cin >> n >> m;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= m; ++j) cin >> a[i][j];
	}
	int q;
	cin >> q;
	while (q--) {
		int x, y;
		cin >> x >> y;
		a[x][y] = 1;
		queue <pair <int, int> > q;
		q.push({1, 1});
		used[1][1] = 1;
		while (!q.empty()) {
			int i = q.front().first;
			int j = q.front().second;
			q.pop();
			if (i < n && !used[i + 1][j] && !a[i + 1][j]) {
				used[i + 1][j] = 1;
				q.push({i + 1, j});
			}
			if (j < m && !used[i][j + 1] && !a[i][j + 1]) {
				used[i][j + 1] = 1;
				q.push({i, j + 1});
			}
		}
		if (used[n][m]) 
			cout << "1\n";
		else {
			cout << "0\n";
			a[x][y] = 0;
		}
		for (int i = 1; i <= n; ++i) {
			for (int j = 1; j <= m; ++j) used[i][j] = 0;
		}
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 588 KB Output is correct
2 Correct 23 ms 844 KB Output is correct
3 Correct 97 ms 912 KB Output is correct
4 Correct 148 ms 844 KB Output is correct
5 Correct 166 ms 844 KB Output is correct
6 Correct 289 ms 876 KB Output is correct
7 Correct 102 ms 844 KB Output is correct
8 Correct 146 ms 876 KB Output is correct
9 Correct 379 ms 888 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 588 KB Output is correct
2 Correct 23 ms 844 KB Output is correct
3 Correct 97 ms 912 KB Output is correct
4 Correct 148 ms 844 KB Output is correct
5 Correct 166 ms 844 KB Output is correct
6 Correct 289 ms 876 KB Output is correct
7 Correct 102 ms 844 KB Output is correct
8 Correct 146 ms 876 KB Output is correct
9 Correct 379 ms 888 KB Output is correct
10 Correct 4145 ms 1144 KB Output is correct
11 Correct 166 ms 612 KB Output is correct
12 Execution timed out 5065 ms 7136 KB Time limit exceeded
13 Halted 0 ms 0 KB -