oj.uz

답안 #961769

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961769 2024-04-12T12:20:28 Z pcc Furniture (JOI20_furniture) C++17
100 / 100
 506 ms 63512 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>


const int mxn = 1010;
bitset<mxn> dp[2][mxn];
bitset<mxn> able[mxn];
int N,M,Q;
set<pii> alive[mxn*2];
int arr[mxn][mxn];


namespace INIT{
	void GO(){
		dp[0][1][1] = dp[1][1][1] = 1;
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=M;j++){
				if(i==1&&j==1)continue;
				if(!arr[i][j])continue;
				dp[0][i][j] = (dp[0][i-1][j]|dp[0][i][j-1]);
			}
			for(int j = 1;j<=M;j++){
				if(i==1&&j==1)continue;
				if(!arr[N+1-i][M+1-j])continue;
				dp[1][i][j] = (dp[1][i-1][j]|dp[1][i][j-1]);
			}
		}
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=M;j++){
				if(dp[0][i][j]&&dp[1][N+1-i][M+1-j]){
					able[i][j] = true;
					alive[i+j].insert(pii(i,j));
				}
			}
		}
		return;
	}
}

namespace QUERY{
	queue<pii> q;
	void del(int sx,int sy){
		able[sx][sy] = false;
		alive[sx+sy].erase(pii(sx,sy));
		q.push(pii(sx,sy));
		while(!q.empty()){
			auto [r,c] = q.front();
			q.pop();
			alive[r+c].erase(pii(r,c));
			if(able[r+1][c]&&!able[r+1][c-1]){
				able[r+1][c] = false;
				alive[r+c+1].erase(pii(r+1,c));
				q.push(pii(r+1,c));
			}
			if(able[r][c+1]&&!able[r-1][c+1]){
				able[r][c+1] = false;
				alive[r+c+1].erase(pii(r,c+1));
				q.push(pii(r,c+1));
			}
			if(able[r][c-1]&&!able[r+1][c-1]){
				able[r][c-1] = false;
				alive[r+c-1].erase(pii(r,c-1));
				q.push(pii(r,c-1));
			}
			if(able[r-1][c]&&!able[r-1][c+1]){
				able[r-1][c] = false;
				alive[r+c-1].erase(pii(r-1,c));
				q.push(pii(r-1,c));
			}
		}
		return;
	}
	void solve(int r,int c){
		if(!able[r][c]){
			cout<<"1\n";
			return;
		}
		if(alive[r+c].size() == 1){
			cout<<"0\n";
			return;
		}
		cout<<"1\n";
		del(r,c);
		/*
		for(int i = 1;i<=N;i++){
			for(int j = 1;j<=M;j++)cerr<<able[i][j];cerr<<endl;
		}
	   */
		return;
	}
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>N>>M;
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)cin>>arr[i][j],arr[i][j] ^= 1;
	}
	INIT::GO();
	/*
	for(int i = 1;i<=N;i++){
		for(int j = 1;j<=M;j++)cerr<<able[i][j];
		cerr<<endl;
	}

   */
	cin>>Q;
	while(Q--){
		int r,c;
		cin>>r>>c;
		QUERY::solve(r,c);
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 3 ms 5164 KB Output is correct
6 Correct 4 ms 5328 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 4 ms 5212 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct

Subtask #2
95.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 4952 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 3 ms 4956 KB Output is correct
4 Correct 3 ms 4952 KB Output is correct
5 Correct 3 ms 5164 KB Output is correct
6 Correct 4 ms 5328 KB Output is correct
7 Correct 4 ms 5212 KB Output is correct
8 Correct 4 ms 5212 KB Output is correct
9 Correct 4 ms 5212 KB Output is correct
10 Correct 6 ms 4956 KB Output is correct
11 Correct 5 ms 4956 KB Output is correct
12 Correct 440 ms 45276 KB Output is correct
13 Correct 172 ms 31992 KB Output is correct
14 Correct 503 ms 49264 KB Output is correct
15 Correct 498 ms 54320 KB Output is correct
16 Correct 368 ms 58564 KB Output is correct
17 Correct 403 ms 61348 KB Output is correct
18 Correct 506 ms 60292 KB Output is correct
19 Correct 407 ms 63512 KB Output is correct
20 Correct 378 ms 63476 KB Output is correct
21 Correct 452 ms 63312 KB Output is correct