oj.uz

Submission #601914

# Submission time Handle Problem Language Result Execution time Memory
601914 2022-07-22T12:12:48 Z ignus Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 45264 KB 
#include<bits/stdc++.h>
using namespace std;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	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-1][x-1]=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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 5 ms 468 KB Output is correct
10 Correct 12 ms 1136 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 219 ms 14952 KB Output is correct
13 Correct 74 ms 11652 KB Output is correct
14 Correct 338 ms 13368 KB Output is correct
15 Correct 330 ms 14164 KB Output is correct
16 Execution timed out 5055 ms 45264 KB Time limit exceeded
17 Halted 0 ms 0 KB -