Submission #583086

#	Time	Username	Problem	Language	Result	Execution time	Memory
583086		penguinhacker	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	596 KiB

furniture

#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 / 5
• Subtask 2: 0 / 95