Submission #904121

#	Time	Username	Problem	Language	Result	Execution time	Memory
904121		dsyz	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	348 KiB

furniture

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N,M;
	cin>>N>>M;
	ll cnt[N + M + 5];
	memset(cnt,0,sizeof(cnt));
	bool R[N][M];
	vector<pair<pair<ll,ll>,bool> > updates;
	for(ll i = 0;i < N;i++){
		for(ll j = 0;j < M;j++){
			cin>>R[i][j];
			cnt[i + j]++;
			if(R[i][j] == 1){
				updates.push_back({{i,j},0});
			}
		}
	}
	ll Q;
	cin>>Q;
	int Hy[] = {0,-1};
	int Wx[] = {-1,0};
	for(ll i = 0;i < Q;i++){
		ll A,B;
		cin>>A>>B;
		A--, B--;
		updates.push_back({{A,B},1});
	}
	for(auto u : updates){
		ll A = u.first.first;
		ll B = u.first.second;
		bool notoriginal = u.second;
		if(R[A][B] == 1 || cnt[A + B] == 1){
			if(notoriginal) cout<<0<<'\n';
		}else{
			queue<pair<ll,ll> > q;
			R[A][B] = 1;
			q.push({A,B});
			bool ok = 1;
			while(!q.empty()){
				ll y = q.front().first;
				ll x = q.front().second;
				q.pop();
				if(cnt[y + x] == 1){
					ok = 0;
					break; //all paths pass through (A,B) so cannot cover (A,B), can prove that leaving at least 1 path that pass through (A,B) will not affect future queries (so no need to undo)
				}
				cnt[y + x]--;
				for(ll i = 0;i < 2;i++){
					ll r = y + Hy[i];
					ll c = x + Wx[i];
					if(r < 0 || r >= N || c < 0 || c >= M || R[r][c] == 1){
						continue;
					}
					bool blocked1 = 1; //no path from (r,c) to (N-1,M-1)
					if(r < N - 1 && R[r + 1][c] == 0){
						blocked1 = 0;
					}
					if(c < M - 1 && R[r][c + 1] == 0){
						blocked1 = 0;
					}
					bool blocked2 = 1; //no path from (0,0) to (r,c)
					if(r >= 1 && R[r - 1][c] == 0){
						blocked2 = 0;
					}
					if(c >= 1 && R[r][c - 1] == 0){
						blocked2 = 0;
					}
					if(blocked1 || blocked2){
						R[r][c] = 1;
						q.push({r,c});
					}
				}
			}
			if(ok){
				if(notoriginal) cout<<1<<'\n';
			}else{
				if(notoriginal) cout<<0<<'\n';
			}
		}
	}
}

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