oj.uz

Submission #412256

# Submission time Handle Problem Language Result Execution time Memory
412256 2021-05-26T16:08:51 Z CSQ31 Furniture (JOI20_furniture) C++14
100 / 100
 449 ms 20776 KB 
#pragma GCC optimize("Ofast") 
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e8)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
vii vis(1111,vector<int>(1111));
int n,m;
int main()
{
	owo
	cin>>n>>m;
	vector<int>cnt(n+m+1);
	vii f(n+1,vector<int>(m+1));
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>vis[i][j];	
			f[i][j] = 1;
			cnt[i+j]++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(vis[i][j]){
				if(!f[i][j])continue;
				f[i][j]=0;
				cnt[i+j]--;
				queue<pii>q;
				q.push({i-1,j});
				q.push({i,j-1});
				while(!q.empty()){
					int x = q.front().fi;
					int y = q.front().se;
					q.pop();
					if(x<0 || x>n || y<0 || y>m || !f[x][y])continue;
					if( (x==n  || !f[x+1][y]) && (y ==m || !f[x][y+1])){
						f[x][y] = 0;
						cnt[x+y]--;
						q.push({x-1,y});
						q.push({x,y-1});
					}
				}	
				q.push({i+1,j});
				q.push({i,j+1});
				while(!q.empty()){
					int x = q.front().fi;
					int y = q.front().se;
					q.pop();
					if(x<0 || x>n || y<0 || y>m || !f[x][y])continue;
					if( (!x || !f[x-1][y]) && (!y || !f[x][y-1])){
						f[x][y] = 0;
						cnt[x+y]--;
						q.push({x+1,y});
						q.push({x,y+1});
					}
				}	
				
				
			}
			
		}
	}
	int Q;
	cin>>Q;
	while(Q--){
		int i,j;
		cin>>i>>j;
		if(!f[i][j] || cnt[i+j] > 1){
			cout<<1<<'\n';
			if(!f[i][j])continue;
			f[i][j]=0;
			cnt[i+j]--;
			queue<pii>q;
			q.push({i-1,j});
			q.push({i,j-1});
			while(!q.empty()){
				int x = q.front().fi;
				int y = q.front().se;
				q.pop();
				if(x<0 || x>n || y<0 || y>m || !f[x][y])continue;
				if( (x==n  || !f[x+1][y]) && (y ==m || !f[x][y+1])){
					f[x][y] = 0;
					cnt[x+y]--;
					q.push({x-1,y});
					q.push({x,y-1});
				}
			}	
			q.push({i+1,j});
			q.push({i,j+1});
			while(!q.empty()){
				int x = q.front().fi;
				int y = q.front().se;
				q.pop();
				if(x<0 || x>n || y<0 || y>m || !f[x][y])continue;
				if( (!x || !f[x-1][y]) && (!y || !f[x][y-1])){
					f[x][y] = 0;
					cnt[x+y]--;
					q.push({x+1,y});
					q.push({x,y+1});
				}
			}	
		}else cout<<0<<'\n';
	}

}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 7 ms 5196 KB Output is correct
5 Correct 6 ms 5212 KB Output is correct
6 Correct 7 ms 5324 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 7 ms 5324 KB Output is correct
9 Correct 7 ms 5324 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5196 KB Output is correct
2 Correct 5 ms 5196 KB Output is correct
3 Correct 5 ms 5196 KB Output is correct
4 Correct 7 ms 5196 KB Output is correct
5 Correct 6 ms 5212 KB Output is correct
6 Correct 7 ms 5324 KB Output is correct
7 Correct 9 ms 5332 KB Output is correct
8 Correct 7 ms 5324 KB Output is correct
9 Correct 7 ms 5324 KB Output is correct
10 Correct 16 ms 5696 KB Output is correct
11 Correct 6 ms 5196 KB Output is correct
12 Correct 220 ms 13492 KB Output is correct
13 Correct 91 ms 10428 KB Output is correct
14 Correct 418 ms 18172 KB Output is correct
15 Correct 365 ms 18380 KB Output is correct
16 Correct 375 ms 19308 KB Output is correct
17 Correct 410 ms 20164 KB Output is correct
18 Correct 407 ms 19784 KB Output is correct
19 Correct 437 ms 20620 KB Output is correct
20 Correct 357 ms 20776 KB Output is correct
21 Correct 449 ms 20720 KB Output is correct