Submission #541496

#	Time	Username	Problem	Language	Result	Execution time	Memory
541496		xuliu	Furniture (JOI20_furniture)	C++17	100 / 100	391 ms	12848 KiB

furniture

#include <bits/stdc++.h>

using namespace std;

#define ll long long 
#define ld long double 
#define debug if(0)

const int N = 1e3 + 4;
int n, m;
bool good[N][N]; // 0 - not good, 1 - good [ good - is path from (1, 1) - (x, y) - (n, m)
int cnt[2*N+4]; // how many good cells with X+Y = i

bool nin(int x, int y) {
	return x < 1 || x > n || y < 1 || y > m;
}

void dfs(int x, int y, bool up=0) {
	if(nin(x, y)) return;
	if(!good[x][y]) return;
	if(up && (good[x+1][y] || good[x][y+1])) return;
	if(!up && (good[x-1][y] || good[x][y-1])) return;
	good[x][y] = 0; cnt[x+y]--;
	debug cerr<<"{"<<x<<", "<<y<<"} is bad, so cnt["<<x+y<<"] = "<<cnt[x+y]<<"\n";
	if(!up) {
		dfs(x+1, y, up);
		dfs(x, y+1, up);
	}
	else {
		dfs(x-1, y, up);
		dfs(x, y-1, up);
	}
}

void upd(int x, int y, bool print) {
	bool ok = 1;
	if(good[x][y] && cnt[x+y] == 1) ok = 0;
	if(ok && good[x][y]) {
		good[x][y] = 0; cnt[x+y]--;
		dfs(x+1, y);
		dfs(x, y+1);
		dfs(x-1, y, 1);
		dfs(x, y-1, 1);
	}
	if(print) cout<<ok<<"\n";
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m;
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			good[i][j] = 1;
			cnt[i+j]++;
		}
	}
	for(int i=1; i<=n; i++) {
		for(int j=1; j<=m; j++) {
			int c; cin>>c;
			if(c == 1) upd(i, j, 0);
		}
	}
	int q; cin>>q;
	while(q--) {
		int x, y; cin>>x>>y;
		upd(x, y, 1);
	}
}

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