Submission #918754

#	Time	Username	Problem	Language	Result	Execution time	Memory
918754		waldi	Furniture (JOI20_furniture)	C++17	100 / 100	241 ms	15960 KiB

furniture

#include <bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define ssize(x) (int(x.size()))
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	vector czy(n, vector(m, 1));
	vector suma(n+m-1, 0);
	REP(i, n) REP(j, m) ++suma[i+j];
	
	auto usun = [&](int si, int sj){
		if(!czy[si][sj]) return;
		czy[si][sj] = 0;
		--suma[si+sj];
		
		queue<pii> q;
		q.emplace(si+1, sj);
		q.emplace(si, sj+1);
		while(ssize(q)){
			auto [i, j] = q.front(); q.pop();
			if(i<0 || j<0 || i>=n || j>=m || !czy[i][j]) continue;
			if(i && czy[i-1][j]) continue;
			if(j && czy[i][j-1]) continue;
			czy[i][j] = 0;
			--suma[i+j];
			q.emplace(i+1, j);
			q.emplace(i, j+1);
		}
		
		q.emplace(si-1, sj);
		q.emplace(si, sj-1);
		while(ssize(q)){
			auto [i, j] = q.front(); q.pop();
			if(i<0 || j<0 || i>=n || j>=m || !czy[i][j]) continue;
			if(i+1<n && czy[i+1][j]) continue;
			if(j+1<m && czy[i][j+1]) continue;
			czy[i][j] = 0;
			--suma[i+j];
			q.emplace(i-1, j);
			q.emplace(i, j-1);
		}
	};
	
	auto niemoge = [&](int i, int j){
		if(!czy[i][j]) return false;
		return suma[i+j] == 1;
	};
	
	REP(i, n) REP(j, m){
		int a;
		scanf("%d", &a);
		if(a) usun(i, j);
	}
	
	int q;
	scanf("%d", &q);
	while(q--){
		int i, j;
		scanf("%d%d", &i, &j);
		--i, --j;
		if(niemoge(i, j)) printf("0\n");
		else usun(i, j), printf("1\n");
	}
	return 0;
}

Compilation message (stderr)

furniture.cpp: In function 'int main()':
furniture.cpp:13:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
furniture.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |   scanf("%d", &a);
      |   ~~~~~^~~~~~~~~~
furniture.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
furniture.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |   scanf("%d%d", &i, &j);
      |   ~~~~~^~~~~~~~~~~~~~~~

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