Submission #968849

#	Time	Username	Problem	Language	Result	Execution time	Memory
968849		happy_node	Furniture (JOI20_furniture)	C++17	0 / 100	4 ms	12916 KiB

furniture

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

const int MX=1005;

int N,M,Q;
int C[MX][MX], A[MX][MX], D[MX][MX];
pair<int,int> qp[MX*MX];
vector<pair<int,int>> vec[2*MX];
bool ans[MX][MX];

bool reach0[MX][MX], reach1[MX][MX];

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

	memset(A,-1,sizeof A);
	memset(D,-1,sizeof D);

	cin>>N>>M;

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

	// correct the grid such that every (x,y) s.t. A(x,y)=0 can both reach end and be reached from start

	{
		queue<pair<int,int>> q;
		q.push({1,1});
		while(!q.empty()) {
			auto [x,y]=q.front(); q.pop();
			if(reach0[x][y]) continue;

			reach0[x][y]=1;
			// down
			if(x+1<=N && !C[x+1][y]) {
				q.push({x+1,y});
			}

			// right
			if(y+1<=M && !C[x][y+1]) {
				q.push({x,y+1});
			}
		}

		q.push({N,M});
		while(!q.empty()) {
			auto [x,y]=q.front(); q.pop();
			if(reach1[x][y]) continue;

			reach1[x][y]=1;
			// up
			if(x-1>0 && !C[x-1][y]) {
				q.push({x-1,y});
			}

			// left
			if(y-1>0 && !C[x][y-1]) {
				q.push({x,y-1});
			}
		}
	}

	for(int i=1;i<=N;i++) {
		for(int j=1;j<=M;j++) {
			if(!(reach0[i][j] && reach1[i][j])) C[i][j]=1;
			if(C[i][j]) A[i][j]=0;
		}
	}

	cin>>Q;
	for(int i=1;i<=Q;i++) {
		int x,y;
		cin>>x>>y;

		if(A[x][y]!=0)
			A[x][y]=i;

		qp[i]=make_pair(x,y);
	}

	int lst=0;

	D[1][1]=0;
	vec[0].push_back({1,1});

	for(int t=1;t<=N*M;t++) {
		if(lst==N+M-2) break;
		queue<pair<int,int>> q;

		for(auto [x,y]:vec[lst]) {
			q.push({x,y});
		}

		while(!q.empty()) {
			auto [x,y]=q.front(); q.pop();
			lst=D[x][y];
			vec[D[x][y]].push_back({x,y});
			// down
			if(x+1<=N && A[x+1][y]==-1 && D[x+1][y]==-1) {
				D[x+1][y]=D[x][y]+1;
				q.push({x+1,y});
			}

			// right
			if(y+1<=M && A[x][y+1]==-1 && D[x][y+1]==-1) {
				D[x][y+1]=D[x][y]+1;
				q.push({x,y+1});
			}
		}	

		if(lst==N+M-2) break;

		int wx=0,wy=0,wt=0;	
		for(auto [x,y]:vec[lst]) {
			// down
			if(x+1<=N && A[x+1][y]>wt) {
				wt=A[x+1][y];
				wx=x+1;
				wy=y;
			}

			// right
			if(y+1<=M && A[x][y+1]>wt) {
				wt=A[x][y+1];
				wx=x;
				wy=y+1;
			}
		}
		assert(wx!=0);
		assert(A[wx][wy]!=0);

		A[wx][wy]=-1;
		ans[wx][wy]=1;	
		D[wx][wy]=lst+1;
		lst+=1;
		vec[D[wx][wy]].push_back({wx,wy});
	}	

	for(int i=1;i<=Q;i++) {
		auto [x,y]=qp[i];
		cout<<(ans[x][y]^1)<<'\n';
	}
}

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