oj.uz

Submission #534757

# Submission time Handle Problem Language Result Execution time Memory
534757 2022-03-08T18:46:28 Z michao Furniture (JOI20_furniture) C++14
100 / 100
 494 ms 27672 KB 
#include <bits/stdc++.h>
#define int long long
#define mp make_pair
#define pb push_back
#define ld long double
#define pii pair<int,int>
#define sz(x) (int)x.size()
#define piii pair<pii,pii>
#define precise cout<<fixed<<setprecision(10)
#define st first
#define nd second
#define ins insert
#define vi vector<int>
#define BOOST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
const int MAX=1e3+5;
int a[MAX][MAX];
int dp[MAX][MAX]; // czy istnieje sciezka przechodzaca przez punkt, 0 jesli tak 1 jesli nie
int n,m;
int ile[MAX+MAX];
bool check(int x,int y){
	if (ile[x+y]==1 && dp[x][y]==0)return false;
	return true;
}

void zaznacz(int x,int y){
  assert(check(x,y));
  if (dp[x][y]==0)
  ile[x+y]--;
	a[x][y]=1;
	dp[x][y]=1;
}

bool check2(int x,int y){
	return x>=1 && x<=n && y>=1 && y<=m;
}

bool blocked(int x,int y){
	if (dp[x][y]==1)return false;
	if (dp[x-1][y]==1 && dp[x][y-1]==1 && (x>1 || y>1))return true;
	if (dp[x+1][y]==1 && dp[x][y+1]==1 && (x<n || y<m))return true;
	return false;
}

int px[4]={1,-1,0,0};
int py[4]={0,0,-1,1};
void block(int x,int y){
	assert(check(x,y));
	queue<pii>q;
	zaznacz(x,y);
	q.push(mp(x,y));
	while (!q.empty()){
		x=q.front().st;
		y=q.front().nd;
		q.pop();
		for (int i=0;i<4;i++){
			int tox=x+px[i];
			int toy=y+py[i];
			if (!check2(tox,toy))continue;
			if (blocked(tox,toy)){
				assert(tox>1 || toy>1);
				zaznacz(tox,toy);
				q.push(mp(tox,toy));
			}
		}
	}
}
int32_t main(){
  BOOST;
  cin>>n>>m;
  for (int i=0;i<=MAX-1;i++)for (int j=0;j<=MAX-1;j++){
		dp[i][j]=1;
  }
  for (int i=1;i<=n;i++)for (int j=1;j<=m;j++)dp[i][j]=0,ile[i+j]++;
  for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			cin>>a[i][j];
		}
  }
  
  for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++){
			if (a[i][j]==1){
				if (check(i,j))
					block(i,j);
			}
		}
  }
  int t;
  cin>>t;
  for (int z=0;z<t;z++){
		int x,y;
		cin>>x>>y;
		if (check(x,y)){
			block(x,y);
			cout<<"1\n";
		}
		else cout<<"0\n";
  }
  return 0; 
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8524 KB Output is correct
2 Correct 7 ms 8700 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8780 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 7 ms 8780 KB Output is correct
7 Correct 7 ms 8780 KB Output is correct
8 Correct 7 ms 8816 KB Output is correct
9 Correct 7 ms 8780 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8524 KB Output is correct
2 Correct 7 ms 8700 KB Output is correct
3 Correct 6 ms 8652 KB Output is correct
4 Correct 6 ms 8780 KB Output is correct
5 Correct 7 ms 8780 KB Output is correct
6 Correct 7 ms 8780 KB Output is correct
7 Correct 7 ms 8780 KB Output is correct
8 Correct 7 ms 8816 KB Output is correct
9 Correct 7 ms 8780 KB Output is correct
10 Correct 15 ms 9012 KB Output is correct
11 Correct 6 ms 8524 KB Output is correct
12 Correct 201 ms 20556 KB Output is correct
13 Correct 78 ms 17540 KB Output is correct
14 Correct 427 ms 24980 KB Output is correct
15 Correct 412 ms 25224 KB Output is correct
16 Correct 465 ms 26324 KB Output is correct
17 Correct 494 ms 27240 KB Output is correct
18 Correct 390 ms 26652 KB Output is correct
19 Correct 420 ms 27656 KB Output is correct
20 Correct 294 ms 27644 KB Output is correct
21 Correct 410 ms 27672 KB Output is correct