Submission #1039317

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039317		1L1YA	Furniture (JOI20_furniture)	C++17	100 / 100	203 ms	25940 KiB

furniture

//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=1011;
const int lg=23;

int n,m,q,x[4]={1,0,-1,0},y[4]={0,1,0,-1},cnt[N<<1],a[N][N],c[2][N][N];
bool mark[2][N][N];

void bfs(int ind,pii s){
	queue<pii> Q;
	Q.push(s);
	mark[ind][s.F][s.S]=1;
	while(!Q.empty()){
		int p=Q.front().F,q=Q.front().S;Q.pop();
		for(int i=0+ind*2;i<2+ind*2;i++)
			if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && !a[p+x[i]][q+y[i]]){
				c[ind][p+x[i]][q+y[i]]++;
				if(!mark[ind][p+x[i]][q+y[i]]){
					mark[ind][p+x[i]][q+y[i]]=1;
					Q.push({p+x[i],q+y[i]});
				}
			}
	}
}

void BFS(int ind,pii s){
	queue<pii> Q;
	Q.push(s);
	mark[ind][s.F][s.S]=0;
	while(!Q.empty()){
		int p=Q.front().F,q=Q.front().S;Q.pop();
		for(int i=0+ind*2;i<2+ind*2;i++)
			if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && mark[0][p+x[i]][q+y[i]] && mark[1][p+x[i]][q+y[i]]){
				c[ind][p+x[i]][q+y[i]]--;
				if(!c[ind][p+x[i]][q+y[i]]){
					cnt[p+q+x[i]+y[i]]--;
					mark[ind][p+x[i]][q+y[i]]=0;
					Q.push({p+x[i],q+y[i]});
				}
			}
	}
}

int main(){
	FastIO

	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> a[i][j];
	bfs(0,{1,1});
	bfs(1,{n,m});
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mark[0][i][j] && mark[1][i][j])
				cnt[i+j]++;
	cin >> q;
	while(q--){
		int X,Y;
		cin >> X >> Y;
		if(!mark[0][X][Y] || !mark[1][X][Y]){
			cout << 1 << endl;
			continue;
		}
		if(cnt[X+Y]==1){
			cout << 0 << endl;
			continue;
		}
		cout << 1 << endl;
		cnt[X+Y]--;
		BFS(0,{X,Y});
		BFS(1,{X,Y});
	}

	return 0;
}

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