oj.uz

답안 #601943

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
601943 2022-07-22T12:47:19 Z ignus Furniture (JOI20_furniture) C++14
5 / 100
 5000 ms 46292 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;
				int ty=y-1; int tx=x-1;
				while((ty==n-1||!a[ty+1][tx])^(tx==m-1||!a[ty][tx+1])){
					if(checked[ty][tx]) break;
					checked[ty][tx]=1;
					if(a[ty+1][tx]) ty++;
					else if(a[ty][tx+1]) tx++;
				}
				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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 604 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 3 ms 508 KB Output is correct
4 Correct 3 ms 468 KB Output is correct
5 Correct 5 ms 468 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 4 ms 604 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 1240 KB Output is correct
11 Correct 3 ms 468 KB Output is correct
12 Correct 227 ms 15860 KB Output is correct
13 Correct 85 ms 12408 KB Output is correct
14 Correct 365 ms 14264 KB Output is correct
15 Correct 336 ms 15080 KB Output is correct
16 Execution timed out 5036 ms 46292 KB Time limit exceeded
17 Halted 0 ms 0 KB -