oj.uz

Submission #391159

# Submission time Handle Problem Language Result Execution time Memory
391159 2021-04-18T06:19:01 Z keta_tsimakuridze Furniture (JOI20_furniture) C++14
5 / 100
 1990 ms 32504 KB 
#include<bits/stdc++.h>
#define f first
#define int long long
#define s second
using namespace std;
const int N=1005,mod=1e9+7;
int t,d2[N][N],d1[N][N],p[N][N],n,m,cnt[N];
queue<pair<int,int> > q;
char c[N][N];
bool ok(int x,int y){
	if(min(x,y)<1 || x>n || y>m) return 0;
	return 1;
}
void dfs1(int x,int y){
	if(d1[x][y] || c[x][y]=='1') return;
	d1[x][y]=1;
	if(ok(x+1,y)) dfs1(x+1,y);
	if(ok(x,y+1)) dfs1(x,y+1);
}
void dfs2(int x,int y){
	if(d2[x][y] || c[x][y]=='1') return;
	d2[x][y]=1; 
	if(ok(x-1,y)) dfs2(x-1,y);
	if(ok(x,y-1)) dfs2(x,y-1);
}
void update1(int x,int y){
	if(ok(x+1,y) && p[x+1][y] && !p[x+1][y-1]) q.push({x+1,y});	
	if(ok(x,y+1) && p[x][y+1] && !p[x-1][y+1]) q.push({x,y+1});	
	while(q.size()){
		x=q.front().f;
		y=q.front().s;
		q.pop();
		if(p[x][y-1] || p[x-1][y]) continue;
		p[x][y]=0; cnt[x+y]--;
		if(ok(x+1,y) && p[x+1][y] && !p[x+1][y-1]) q.push({x+1,y});	
		if(ok(x,y+1) && p[x][y+1] && !p[x-1][y+1]) q.push({x,y+1});	
	}
}
void update2(int x,int y){
	if(ok(x-1,y) && p[x-1][y] && !p[x-1][y+1]) q.push({x-1,y});	
	if(ok(x,y-1) && p[x][y-1] && !p[x+1][y-1]) q.push({x,y-1});	
	while(q.size()){
		x=q.front().f;
		y=q.front().s;
		q.pop();
		if(p[x][y+1] || p[x+1][y]) continue;
		p[x][y]=0; cnt[x+y]--;
		if(ok(x-1,y) && p[x-1][y] && !p[x-1][y+1]) q.push({x-1,y});	
		if(ok(x,y-1) && p[x][y-1] && !p[x+1][y-1]) q.push({x,y-1});	
	}
}
 main(){
	// t=1;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
		}
	}
	dfs1(1,1);
	dfs2(n,m); d1[1][1]=d2[n][m]=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(d1[i][j] && d2[i][j]) p[i][j]=1,cnt[i+j]++;
		
		}
	}
	int q;
	cin>>q;
	while(q--){
		int a,b;
		cin>>a>>b;
		if(!p[a][b] ) {
			cout<<1<<endl;
		}
		else {
			if(cnt[a+b]-1){ 
				p[a][b]=0; 
				cnt[a+b]--;
				update1(a,b);
				update2(a,b);
				cout<<1<<endl;
			}
			else cout<<0<<endl;
		}
	}
	
}

Compilation message

furniture.cpp:52:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   52 |  main(){
      |       ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1620 KB Output is correct
2 Correct 8 ms 1612 KB Output is correct
3 Correct 9 ms 1612 KB Output is correct
4 Correct 18 ms 1776 KB Output is correct
5 Correct 20 ms 1872 KB Output is correct
6 Correct 24 ms 1868 KB Output is correct
7 Correct 24 ms 1868 KB Output is correct
8 Correct 27 ms 1868 KB Output is correct
9 Correct 22 ms 1948 KB Output is correct

Subtask #2
0.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1620 KB Output is correct
2 Correct 8 ms 1612 KB Output is correct
3 Correct 9 ms 1612 KB Output is correct
4 Correct 18 ms 1776 KB Output is correct
5 Correct 20 ms 1872 KB Output is correct
6 Correct 24 ms 1868 KB Output is correct
7 Correct 24 ms 1868 KB Output is correct
8 Correct 27 ms 1868 KB Output is correct
9 Correct 22 ms 1948 KB Output is correct
10 Correct 54 ms 1800 KB Output is correct
11 Correct 14 ms 1096 KB Output is correct
12 Correct 796 ms 29056 KB Output is correct
13 Correct 123 ms 25220 KB Output is correct
14 Incorrect 1990 ms 32504 KB Output isn't correct
15 Halted 0 ms 0 KB -