Submission #601913

#	Time	Username	Problem	Language	Result	Execution time	Memory
601913		ignus	Furniture (JOI20_furniture)	C++14	5 / 100	5021 ms	47224 KiB

furniture

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

int main(){
	int n, m;
	cin >> n >> m;
	int a[n][m];
	int up[n][m];
	int left[n][m];
	bool checked[n][m];
	up[0][0]=1;
	left[0][0]=1;
	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			checked[i][j]=0;
			left[i][j]=0;
			up[i][j]=0;
			bool temp;
			cin >> temp;
			a[i][j]=!temp;
		}
	}
	queue<pair<int, int>> q;
	q.push({0,0});
	while(!q.empty()){
		int x=q.front().second, y=q.front().first;
		if(x<m-1&&a[y][x+1]){
			if(!up[y][x+1]){
				q.push({y, x+1});
			}
		//	if(x+1==0)cout << "BLLLARGHHH";
			left[y][x+1]=1;
		}
		if(y<n-1&&a[y+1][x]){
			if(!left[y+1][x]){
				q.push({y+1, x});
			}
			up[y+1][x]=1;
		}
		q.pop();/*
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				cout << a[i][j] <<  left[i][j] <<up[i][j] <<' ';
			}
			cout << '\n';
		}*/
	}
	checked[n-1][m-1]=1;
	int qe;
	cin >> qe;
//	vector<int>aaaaaaaaaa;
	for(int i = 0; i < qe; i++){
		queue<pair<int, pair<int, int>>> forgor;
		int x, y;
		cin >> y >> x;
		if(!a[y-1][x-1]){
			cout << "1\n";
			continue;
		}
		queue<pair<int, int>> qu;
		qu.push({y-1, x-1});
		while(!qu.empty()){
			int y1 = qu.front().first, x1=qu.front().second;
			//cout << y1 << '-' << x1<< ',';
			if(checked[y1][x1]){
			//	checked[y][x]=1;
				while(!forgor.empty()){
					int type=forgor.front().first;
					int y2=forgor.front().second.first;
					int x2=forgor.front().second.second;
					if(type==0) a[y2][x2]=1;
					if(type==1) left[y2][x2]=1;
					if(type==2) up[y2][x2]=1;
					forgor.pop();
				}
				cout << "0\n";
			//	aaaaaaaaaa.push_back(0);
				goto ende;
			}
			qu.pop();
			if(!a[y1][x1]) continue;
			a[y1][x1]=0;
			forgor.push({0, {y1, x1}});
		//	cout << x1 << ' ' << a[y1][x1+1] << ' ' << !up[y1][x1+1] << ' '<<left[y1][x1+1] << ',';
			if(x1<m-1&&a[y1][x1+1]){
				if(!up[y1][x1+1]&&left[y1][x1+1]){
					qu.push({y1, x1+1});
				}
				left[y1][x1+1]=0;
				forgor.push({1, {y1, x1+1}});
			}
			if(y1<n-1&&a[y1+1][x1]){
				if(!left[y1+1][x1]&&up[y1+1][x1]){
					qu.push({y1+1, x1});
				}
				up[y1+1][x1]=0;
				forgor.push({2, {y1+1, x1}});
			}
		}
		cout << "1\n";
		//aaaaaaaaaa.push_back(1);
		ende:
		continue;
	}
/*	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << a[i][j] <<  left[i][j] <<up[i][j] <<' ';
		}
		cout << '\n';
	}
	cout <<"\n\n\n";
	for(int i = 0; i < aaaaaaaaaa.size(); i++){
		cout << aaaaaaaaaa[i] << '\n';
	}*/
	return 0;
}

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