제출 #508782

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
508782		nichke	Furniture (JOI20_furniture)	C++14	100 / 100	381 ms	27852 KiB

furniture

// I may fail a thousand times
// But there is no giving up
// IOI - here I come
#include <bits/stdc++.h>
#define int long long
using namespace std;
queue<int> q;
map<int,int> mp;
int v[(int)1e3+5][(int)1e3+5];
int a[(int)1e3+5][(int)1e3+5];
void push(int x,int y){
	if(a[x][y])return;
	q.push(x);q.push(y);
	a[x][y]=1;
	mp[x+y]--;
}
int upd(int x,int y){
	if(a[x][y])return 1;
	if(mp[x+y]==1)return 0;
	mp[x+y]--;
	a[x][y]=1;
	q.push(x);
	q.push(y);
	for(;!q.empty();){
		int nx=q.front();q.pop();
		int ny=q.front();q.pop();
		if(a[nx+1][ny-1])push(nx+1,ny),push(nx,ny-1);
		if(a[nx-1][ny+1])push(nx-1,ny),push(nx,ny+1);
	}
	return 1;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	memset(a,1,sizeof a);
	int n,m;cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			mp[i+j]++;
			a[i][j]=0;
			cin>>v[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(v[i][j]){
				upd(i,j);
			}
		}
	}
	int q;cin>>q;
	for(;q;q--){
		int x,y;cin>>x>>y;
		cout<<upd(x,y)<<'\n';
	}
	return 0;
}

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