oj.uz

Submission #292585

# Submission time Handle Problem Language Result Execution time Memory
292585 2020-09-07T10:15:07 Z kshitij_sodani Furniture (JOI20_furniture) C++14
100 / 100
 397 ms 18168 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n' 

int n,m;
int it[1001][1001];
int vis[1001][1001];
int vis2[1001][1001];
int val[1001][1001];
int co[3001];

int cal(int i,int j){
	int co=0;
	if(i+1<n){
		co+=val[i+1][j];
	}
	if(j+1<m){
		co+=val[i][j+1];
	}
	return co;
}
int cal2(int i,int j){
	int co=0;
	if(i>0){
		co+=val[i-1][j];
	}
	if(j>0){
		co+=val[i][j-1];
	}
	return co;
}
void dfs(int aa,int bb){
	val[aa][bb]=0;
	co[aa+bb]-=1;
	if(aa>0){
		if(val[aa-1][bb]){
			if(cal(aa-1,bb)==0){
				dfs(aa-1,bb);
			}
		}
	}
	if(bb>0){
		if(val[aa][bb-1]){
			if(cal(aa,bb-1)==0){
				dfs(aa,bb-1);
			}
		}
	}
}
void dfs2(int aa,int bb){
	val[aa][bb]=0;
	co[aa+bb]-=1;
	if(aa<n-1){
		if(val[aa+1][bb]){
			if(cal2(aa+1,bb)==0){
				dfs2(aa+1,bb);
			}
		}
	}
	if(bb<m-1){
		if(val[aa][bb+1]){
			if(cal2(aa,bb+1)==0){
				dfs2(aa,bb+1);
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>it[i][j];
		}
	}
	vis[n-1][m-1]=1;
	for(int i=n-1;i>=0;i--){
		for(int j=m-1;j>=0;j--){
			if(i==n-1 and j==m-1){
				continue;
			}
			if(it[i][j]==0){
				if(i<n-1){
					vis[i][j]|=vis[i+1][j];
				}
				if(j<m-1){
					vis[i][j]|=vis[i][j+1];
				}
			}
		}
	}
	vis2[0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(it[i][j]==1){
				continue;
			}
			if(i==0 and j==0){
				continue;
			}
			if(i>0){
				vis2[i][j]|=vis2[i-1][j];
			}
			if(j>0){
				vis2[i][j]|=vis2[i][j-1];
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(vis2[i][j] and vis[i][j]){
				val[i][j]=1;
				co[i+j]+=1;
			}
		}
	}

	int q;
	cin>>q;
	while(q--){
		int aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		if(val[aa][bb]==0){
			cout<<1<<endl;
			continue;
		}
		if(co[aa+bb]==1){
			cout<<0<<endl;
			continue;
		}
		else{
			dfs(aa,bb);
			dfs2(aa,bb);
			co[aa+bb]+=1;
			cout<<1<<endl;
		}
	}















	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 3 ms 2048 KB Output is correct
3 Correct 3 ms 1792 KB Output is correct
4 Correct 4 ms 1792 KB Output is correct
5 Correct 4 ms 1920 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 4 ms 1920 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 4 ms 1920 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 3 ms 2048 KB Output is correct
3 Correct 3 ms 1792 KB Output is correct
4 Correct 4 ms 1792 KB Output is correct
5 Correct 4 ms 1920 KB Output is correct
6 Correct 5 ms 1920 KB Output is correct
7 Correct 4 ms 1920 KB Output is correct
8 Correct 4 ms 1920 KB Output is correct
9 Correct 4 ms 1920 KB Output is correct
10 Correct 10 ms 1408 KB Output is correct
11 Correct 3 ms 1152 KB Output is correct
12 Correct 184 ms 16552 KB Output is correct
13 Correct 82 ms 15352 KB Output is correct
14 Correct 312 ms 16760 KB Output is correct
15 Correct 324 ms 16760 KB Output is correct
16 Correct 345 ms 17272 KB Output is correct
17 Correct 368 ms 18152 KB Output is correct
18 Correct 397 ms 17400 KB Output is correct
19 Correct 374 ms 18148 KB Output is correct
20 Correct 324 ms 18040 KB Output is correct
21 Correct 370 ms 18168 KB Output is correct