Submission #1289103

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289103		wedonttalkanymore	Furniture (JOI20_furniture)	C++20	100 / 100	258 ms	34024 KiB

furniture

#include <bits/stdc++.h>
/*
    Ngay hay dem
    Voi troi giac mo em dem
*/
using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e3 + 5, inf = 1e18, mod = 1e9 + 7, block = 320, lim = 19;

int n, m, a[N][N];
int q;
int can[N][N][2];
int dx[] = {0, 1, -1, 0}; // phai, duoi, tren, trai
int dy[] = {1, 0, 0, -1};
int pre[N][N];

void bfs(int st1, int st2, int type) {
	can[st1][st2][type] = 1;
	queue <pii> q;
	q.push({st1, st2});
//	cout << "st: " << st1 << ' ' << st2 << '\n';
	while(q.size()) {
		auto [x, y] = q.front();
		q.pop();
//		cout << x << ' ' << y << '\n';
//		cout << type * 2 << '\n';
		for (int i = type * 2; i < type * 2 + 2; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
//			cout << "gg: " << nx << ' ' << ny << '\n';
			if (nx < 1 || nx > n || ny < 1 || ny > m) continue;
			if (a[nx][ny] || can[nx][ny][type]) continue;
			can[nx][ny][type] = 1;
			q.push({nx, ny});
		}
	}
}

int cnt[2 * N];

int dead(int i, int j) {
	if (i < 1 || j < 1 || i > n || j > m) return 0; // 1 la ko dead
	return pre[i][j]; // = 0 la dead, = 1 la ko dead
}

void bfs1(int st1, int st2) {
	queue <pii> q;
	q.push({st1, st2});
	while(q.size()) {
		auto [x, y] = q.front();
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx < 1 || ny < 1 || nx > n || ny > m) continue;
			if (pre[nx][ny] == 0) continue;
			if ((nx == 1 && ny == 1) || (nx == n && ny == m)) continue;
			if (!dead(nx + 1, ny) && !dead(nx, ny + 1)) {
				q.push({nx, ny});
				cnt[nx + ny]--;
				pre[nx][ny] = 0;
				continue;
			}

			if (!dead(nx - 1, ny) && !dead(nx, ny - 1)) {
				q.push({nx, ny});
				cnt[nx + ny]--;
				pre[nx][ny] = 0;
				continue;
			}
		}
	}
}

signed main() {
     ios::sync_with_stdio(false);
     cin.tie(0);
    if (fopen(".inp", "r")) {
        freopen(".inp", "r", stdin);
        freopen(".out", "w", stdout);
    }
    cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
		}
	}
	bfs(1, 1, 0);
	bfs(n, m, 1);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
//			cout << i << ' ' << j << ' ' << can[i][j][0] << ' ' << can[i][j][1] << '\n';
			if (can[i][j][0] && can[i][j][1]) {
				pre[i][j] = 1; // 1 la co nice di qua
				cnt[i + j]++;
//				cout << "at: " << i << ' ' << j << '\n';
			}
		}
	}
	cin >> q;
	for (int i = 1; i <= q; i++) {
		int x, y;
		cin >> x >> y;
		if (pre[x][y] == 0) {
			cout << 1 << '\n';
		}
		else {
			if (cnt[x + y] > 1) {
				cnt[x + y]--;
				pre[x][y] = 0;
				bfs1(x, y);
				cout << 1 << '\n';
			}
			else cout << 0 << '\n';
		}
	}
    return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:85:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |         freopen(".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
furniture.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 95 / 95