oj.uz

답안 #583086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
583086 2022-06-24T19:00:35 Z penguinhacker Furniture (JOI20_furniture) C++17
0 / 100
 1 ms 596 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=1000, dx[8]={-1, -1, -1, 0, 0, 1, 1, 1}, dy[8]={-1, 0, 1, -1, 1, -1, 0, 1};
int n, m, q, c[mxN][mxN], p[mxN*mxN+2];
vector<int> oc[mxN];

int find(int i) {
	return i^p[i]?p[i]=find(p[i]):i;
}

int find(int i, int j) {
	return find(i*m+j);
}

int mrg(int u, int v) {
	if (u<v)
		swap(u, v);
	p[v]=u;
	return u;
}

int prv(int i, int j) {
	if (i==0||j<=1||oc[i-1].empty()||oc[i-1][0]>j-2)
		return -1;
	int pos=upper_bound(oc[i-1].begin(), oc[i-1].end(), j-2)-oc[i-1].begin();
	assert(pos>0);
	return oc[i-1][pos-1];
}

int nxt(int i, int j) {
	if (i==n-1||j+2>=m||oc[i+1].empty()||oc[i+1].back()<j+2)
		return -1;
	auto it=lower_bound(oc[i+1].begin(), oc[i+1].end(), j+2);
	assert(it!=oc[i+1].end());
	return *it;
}

bool bad(int i, int j) {
	bool leftdown=i==n-1||j==0, upright=i==0||j==m-1;
	for (int k=0; k<8; ++k) {
		int ni=i+dx[k], nj=j+dy[k];
		if (0<=ni&&ni<n&&0<=nj&&nj<m&&c[ni][nj]) {
			int u=find(ni, nj);
			if (u==n*m)
				leftdown=1;
			if (u==n*m+1)
				upright=1;
		}
	}
	int x=prv(i, j), y=nxt(i, j);
	if (y!=-1) leftdown|=find(i+1, y)==n*m;
	if (x!=-1) upright|=find(i-1, x)==n*m+1;
	//cout << x << " " << y << " " << leftdown << " " << upright << endl;
	return leftdown&&upright;
}

void add(int i, int j) {
	int u=i*m+j;
	if (i==n-1||j==0)
		u=mrg(u, n*m);
	if (i==0||j==m-1)
		u=mrg(u, n*m+1);
	for (int k=0; k<8; ++k) {
		int ni=i+dx[k], nj=j+dy[k];
		if (0<=ni&&ni<n&&0<=nj&&nj<m&&c[ni][nj]) {
			int v=find(ni, nj);
			if (u!=v)
				u=mrg(u, v);
		}
	}
	int x=prv(i, j), y=nxt(i, j);
	if (y!=-1) {
		int v=find(i+1, y);
		if (u!=v)
			u=mrg(u, v);
	}
	if (x!=-1) {
		int v=find(i-1, x);
		if (u!=v)
			u=mrg(u, v);
	}
	c[i][j]=1;
	oc[i].push_back(j);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	iota(p, p+n*m+2, 0);
	for (int i=0; i<n; ++i)
		for (int j=0; j<m; ++j) {
			cin >> c[i][j];
			if (c[i][j])
				add(i, j);
		}
	cin >> q;
	while(q--) {
		int i, j;
		cin >> i >> j, --i, --j;
		assert(!c[i][j]);
		bool ans=!bad(i, j);
		cout << ans << "\n";
		if (ans)
			add(i, j);
	}
	return 0;
}

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -