oj.uz

Submission #1039317

# Submission time Handle Problem Language Result Execution time Memory
1039317 2024-07-30T17:22:50 Z 1L1YA Furniture (JOI20_furniture) C++17
100 / 100
 203 ms 25940 KB 
//1L1YA

#include<bits/stdc++.h>
using namespace std;

//#pragma GCC optimize ("O3,unrool-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

typedef long long       ll;
typedef pair<ll,ll>     pll;
typedef pair<int,int>   pii;

#define Pb              push_back
#define F               first
#define S               second
#define endl            '\n'
#define sep             ' '
#define all(x)          x.begin(),x.end()
#define al(x,n)         x+1,x+n+1
#define SZ(x)           ((int)x.size())
#define lc              (id<<1)
#define rc              (lc|1)
#define mid             (l+r>>1)
#define dokme(x)        cout << x << endl, exit(0)
#define sik(x)          cout << x << endl;continue;
#define FastIO          ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define FileIO          freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll oo=1e18;
const int mod=1e9+7;
const int inf=1e9+111;
const int N=1011;
const int lg=23;

int n,m,q,x[4]={1,0,-1,0},y[4]={0,1,0,-1},cnt[N<<1],a[N][N],c[2][N][N];
bool mark[2][N][N];

void bfs(int ind,pii s){
	queue<pii> Q;
	Q.push(s);
	mark[ind][s.F][s.S]=1;
	while(!Q.empty()){
		int p=Q.front().F,q=Q.front().S;Q.pop();
		for(int i=0+ind*2;i<2+ind*2;i++)
			if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && !a[p+x[i]][q+y[i]]){
				c[ind][p+x[i]][q+y[i]]++;
				if(!mark[ind][p+x[i]][q+y[i]]){
					mark[ind][p+x[i]][q+y[i]]=1;
					Q.push({p+x[i],q+y[i]});
				}
			}
	}
}

void BFS(int ind,pii s){
	queue<pii> Q;
	Q.push(s);
	mark[ind][s.F][s.S]=0;
	while(!Q.empty()){
		int p=Q.front().F,q=Q.front().S;Q.pop();
		for(int i=0+ind*2;i<2+ind*2;i++)
			if(p+x[i] && p+x[i]<=n && q+y[i] && q+y[i]<=m && mark[0][p+x[i]][q+y[i]] && mark[1][p+x[i]][q+y[i]]){
				c[ind][p+x[i]][q+y[i]]--;
				if(!c[ind][p+x[i]][q+y[i]]){
					cnt[p+q+x[i]+y[i]]--;
					mark[ind][p+x[i]][q+y[i]]=0;
					Q.push({p+x[i],q+y[i]});
				}
			}
	}
}

int main(){
	FastIO

	cin >> n >> m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			cin >> a[i][j];
	bfs(0,{1,1});
	bfs(1,{n,m});
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(mark[0][i][j] && mark[1][i][j])
				cnt[i+j]++;
	cin >> q;
	while(q--){
		int X,Y;
		cin >> X >> Y;
		if(!mark[0][X][Y] || !mark[1][X][Y]){
			cout << 1 << endl;
			continue;
		}
		if(cnt[X+Y]==1){
			cout << 0 << endl;
			continue;
		}
		cout << 1 << endl;
		cnt[X+Y]--;
		BFS(0,{X,Y});
		BFS(1,{X,Y});
	}

	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8536 KB Output is correct
2 Correct 2 ms 10844 KB Output is correct
3 Correct 2 ms 10844 KB Output is correct
4 Correct 3 ms 10844 KB Output is correct
5 Correct 3 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10844 KB Output is correct
10 Correct 7 ms 9052 KB Output is correct
11 Correct 2 ms 6748 KB Output is correct
12 Correct 121 ms 18892 KB Output is correct
13 Correct 49 ms 15960 KB Output is correct
14 Correct 188 ms 23468 KB Output is correct
15 Correct 203 ms 23888 KB Output is correct
16 Correct 195 ms 24720 KB Output is correct
17 Correct 198 ms 25428 KB Output is correct
18 Correct 199 ms 25424 KB Output is correct
19 Correct 202 ms 25940 KB Output is correct
20 Correct 168 ms 25796 KB Output is correct
21 Correct 195 ms 25936 KB Output is correct