oj.uz

Submission #412258

# Submission time Handle Problem Language Result Execution time Memory
412258 2021-05-26T16:10:28 Z CSQ31 Furniture (JOI20_furniture) C++14
100 / 100
 446 ms 19040 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);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>vis[i][j];	
		}
	}
	vii p1(n+1,vector<int>(m+1)),p2(n+1,vector<int>(m+1)),f(n+1,vector<int>(m+1));
	queue<pii>q;
	q.push({1,1});
	p1[1][1] = 1;
	while(!q.empty()){
		pii v = q.front();
		q.pop();
		if(v.fi+1<=n && !p1[v.fi+1][v.se] && !vis[v.fi+1][v.se]){
			p1[v.fi+1][v.se] = 1;
			q.push({v.fi+1,v.se});
		}
		if(v.se+1<=m && !p1[v.fi][v.se+1] && !vis[v.fi][v.se+1]){
			p1[v.fi][v.se+1] = 1;
			q.push({v.fi,v.se+1});
		}
	}
	q.push({n,m});
	p2[n][m] = 1;
	while(!q.empty()){
		pii v = q.front();
		q.pop();
		if(v.fi-1 && !p2[v.fi-1][v.se] && !vis[v.fi-1][v.se]){
			p2[v.fi-1][v.se] = 1;
			q.push({v.fi-1,v.se});
		}
		if(v.se-1 && !p2[v.fi][v.se-1] && !vis[v.fi][v.se-1]){
			p2[v.fi][v.se-1] = 1;
			q.push({v.fi,v.se-1});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(!p1[i][j])continue;
			if(j!=m && p2[i][j+1])f[i][j] = 1;
			if(i!=n && p2[i+1][j])f[i][j] = 1;
			if(i==n && j==m)f[i][j] = 1;
			cnt[i+j]+=f[i][j];
			
		}
	}
	f[n][m] = 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 4 ms 5196 KB Output is correct
3 Correct 5 ms 5312 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 8 ms 5328 KB Output is correct
6 Correct 8 ms 5420 KB Output is correct
7 Correct 8 ms 5324 KB Output is correct
8 Correct 9 ms 5332 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 4 ms 5196 KB Output is correct
3 Correct 5 ms 5312 KB Output is correct
4 Correct 6 ms 5324 KB Output is correct
5 Correct 8 ms 5328 KB Output is correct
6 Correct 8 ms 5420 KB Output is correct
7 Correct 8 ms 5324 KB Output is correct
8 Correct 9 ms 5332 KB Output is correct
9 Correct 7 ms 5324 KB Output is correct
10 Correct 18 ms 5912 KB Output is correct
11 Correct 7 ms 5328 KB Output is correct
12 Correct 239 ms 16960 KB Output is correct
13 Correct 106 ms 15552 KB Output is correct
14 Correct 418 ms 17360 KB Output is correct
15 Correct 380 ms 16836 KB Output is correct
16 Correct 393 ms 17856 KB Output is correct
17 Correct 446 ms 18652 KB Output is correct
18 Correct 416 ms 18432 KB Output is correct
19 Correct 444 ms 19008 KB Output is correct
20 Correct 395 ms 19020 KB Output is correct
21 Correct 434 ms 19040 KB Output is correct