제출 #1180313

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1180313		NAMIN	Furniture (JOI20_furniture)	C++20	100 / 100	290 ms	86080 KiB

furniture

#include <bits/stdc++.h>

#define endl "\n"
#define ll long long

using namespace std;

const int mxN = 1004;
const int LEFT = 3,RIGHT = 1,UP = 0,DOWN=2;
int N,M;
int G[mxN][mxN];
int coli[mxN][mxN][4];
vector<int> depy{-1,0,1,0,1,-1,1};
vector<int> depx{0,-1,0,1,1,1,-1};

bool ok(int x,int y){
	return x >= 0 && x < M && y >= 0 && y < N;
}

void dfs(int x,int y,int val){
	if(coli[y][x][val])
		return;
	coli[y][x][val] = 1;

	for(int d=0;d<7;d++){
		int dx = x+depx[d],dy = y+depy[d];
		if(!ok(dx,dy))
			continue;
		if(!G[dy][dx])
			continue;

		dfs(dx,dy,val);
	}
}

bool case1(int x,int y){
	// return the case :
	// . X
	// X O
	// (O == (x,y) block)
	return (!ok(x,y-1) || G[y-1][x]) && ((!ok(x-1,y) || (G[y][x-1])));
}
bool case2(int x,int y){
	// return the case :
	// O X
	// X .
	// (O == (x,y) block)
	return (!ok(x,y+1) || G[y+1][x]) && ((!ok(x+1,y) || (G[y][x+1])));
}

void fastUpdate(int x,int y){ //make block at (x,y) if case1 or case2
	if(G[y][x])
		return;
	G[y][x] = 1;

	if(ok(x,y+1) && !G[y+1][x] && case1(x,y+1))
		fastUpdate(x,y+1);

	if(ok(x,y-1) && !G[y-1][x] && case2(x,y-1))
		fastUpdate(x,y-1);


	if(ok(x+1,y) && !G[y][x+1] && case1(x+1,y))
		fastUpdate(x+1,y);

	if(ok(x-1,y) && !G[y][x-1] && case2(x-1,y))
		fastUpdate(x-1,y);

}

void slowUpdate(){
	for(int y=0;y<N;y++){
		for(int x=0;x<M;x++){
			if(y == 0 && x == 0)
				continue;
			if(y == N-1 && x == M-1)
				continue;
			
			if((!ok(x,y-1) || G[y-1][x]) && (!ok(x-1,y) || (G[y][x-1]))){
				G[y][x] = 1;
			}
		}
	}


	for(int y=N-1;y>=0;y--){
		for(int x=M-1;x>=0;x--){
			if(y == 0 && x == 0)
				continue;
			if(y == N-1 && x == M-1)
				continue;
			
			if((!ok(x,y+1) || G[y+1][x]) && (!ok(x+1,y) || G[y][x+1])){
				G[y][x] = 1;
			}
		}
	}
}

vector<int> getPotentialInfo(int x,int y){
	vector<int> curcoli(4,0);
	if(y == N-1)
		curcoli[DOWN] = true;
	if(y == 0)
		curcoli[UP] = true;
	if(x == 0)
		curcoli[LEFT] = true;
	if(x == M-1)
		curcoli[RIGHT] = true;
	
	for(int d=0;d<7;d++){
		int dx = x+depx[d],dy = y+depy[d];
		if(!ok(dx,dy))
			continue;
		if(!G[dy][dx])
			continue;
		for(int k=0;k<4;k++){
			curcoli[k] |= coli[dy][dx][k];
		}
	}

	return curcoli;
}

bool check(vector<int> curcoli){
	if(curcoli[LEFT] && curcoli[UP])
		return false;
	else if(curcoli[LEFT] && curcoli[RIGHT])
		return false;
	else if(curcoli[DOWN] && curcoli[UP])
		return false;
	else if(curcoli[RIGHT] && curcoli[DOWN])
		return false;
	return true;
}

void solve(){
	cin >> N >> M;

	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			for(int k=0;k<4;k++){
				coli[i][j][k] = 0;
			}
		}
	}

	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			cin >> G[i][j];
		}
	}

	slowUpdate();
	
	for(int i=0;i<N;i++){// init the information in the blocks 
						 // which touch left and right sides
		if(!coli[i][0][LEFT] && G[i][0])
			dfs(0,i,LEFT);
		if(!coli[i][M-1][RIGHT] && G[i][M-1])
			dfs(M-1,i,RIGHT);
	}
	for(int i=0;i<M;i++){// init the information in the blocks 
						 // which touch down and up sides
		if(!coli[0][i][UP] && G[0][i])
			dfs(i,0,UP);
		if(!coli[N-1][i][DOWN] && G[N-1][i])
			dfs(i,N-1,DOWN);
	}

	int Q;
	cin >> Q;

	while(Q--){
		int y,x;
		cin >> y >> x;
		y--,x--;
		if(G[y][x]){
			cout << 1 << endl;
			continue;
		}

		vector<int> curcoli(4,0);
		curcoli = getPotentialInfo(x,y);
		
		
		bool can = check(curcoli);

		if(can){
			cout << 1 << endl;
			fastUpdate(x,y);
			
			/*for(int i=0;i<N;i++){
				for(int j=0;j<M;j++){
					cout << G[i][j] << ' ';
				}
				cout << endl;
			}*/

			for(int k=0;k<4;k++){// update all adjacent groups informations
				if(curcoli[k]){
					dfs(x,y,k);
				}
			}
		}
		else{
			cout << 0 << endl;
		}
	}

}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	//cin >> t;
 	while(t--){
		solve();
	}
	return 0;
}

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