oj.uz

Submission #601924

# Submission time Handle Problem Language Result Execution time Memory
601924 2022-07-22T12:33:14 Z ignus Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 46280 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];
	bool v[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;
			v[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;
		q.pop();
		if(v[y][x]) continue;
		v[y][x]=1;
		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;
		}/*
		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 3 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 508 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 3 ms 468 KB Output is correct
4 Correct 5 ms 468 KB Output is correct
5 Correct 3 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 5 ms 596 KB Output is correct
8 Correct 4 ms 596 KB Output is correct
9 Correct 5 ms 508 KB Output is correct
10 Correct 13 ms 1236 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 256 ms 15964 KB Output is correct
13 Correct 90 ms 12416 KB Output is correct
14 Correct 412 ms 14400 KB Output is correct
15 Correct 403 ms 15064 KB Output is correct
16 Execution timed out 5039 ms 46280 KB Time limit exceeded
17 Halted 0 ms 0 KB -