Submission #495696

#	Time	Username	Problem	Language	Result	Execution time	Memory
495696		minhcool	Furniture (JOI20_furniture)	C++17	0 / 100	7 ms	460 KiB

furniture

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;

const int N = 1e3 + 5;

const int oo = 1e18 + 7, mod = 1e9 + 7;

int n, m, q;

char c[N][N];

int sz[N * N], rt[N * N];

int root(int x){
	return (x == rt[x] ? x : rt[x] = root(rt[x]));
}

void merge(int x, int y){
	x = root(x);
	y = root(y);
	if(x == y) return;
	if(sz[x] < sz[y]) swap(x, y);
	if(y > n * m) swap(x, y);
	rt[y] = x;
	sz[x] += sz[y];
}

int xx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int yy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

bool upd(int x, int y){
	//cout << "BEGIN\n";
	set<int> se;
	for(int i = 0; i < 8; i++){
		int tempx = x + xx[i], tempy = y + yy[i];
		//cout << tempx << " " << tempy << "\n";
		if(!c[tempx][tempy]) continue;
		//cout << i << "\n";
		if(root((tempx - 1) * m + tempy) > n * m) se.insert(root((tempx - 1) * m + tempy));
	}
	//cout << se.size() << "\n";
	if(x == 1) se.insert(n * m + 1);
	if(y == m) se.insert(n * m + 2);
	if(x == n) se.insert(n * m + 3);
	if(y == 1) se.insert(n * m + 4);
	//cout << se.size() << "\n";
	//for(auto it : se) cout << it << " ";
	//cout << "\n";
	//cout << "END1\n";
	if(se.size() > 1){
		if(se.size() > 2) return 0;
		//cout << (*se.begin()) << " " << (*se.rbegin()) << "\n";
		if((*se.begin()) == (n * m + 1) && (*se.rbegin()) == (n * m + 2)){}
		else if((*se.begin()) == (n * m + 3) && (*se.rbegin()) == (n * m + 4)){}
		else return 0;
	}
	//cout << "OK\n";
	if(x == 1){
		rt[y] = root(n * m + 1);
		sz[root(n * m + 1)]++;
		if(y == m) merge(n * m + 1, n * m + 2);
	}
	else if(x == n){
		rt[(x - 1) * m + y] = root(n * m + 3);
		sz[root(n * m + 3)]++;
		if(y == 1) merge(n * m + 3, n * m + 4);
	}
	else if(y == 1){
		rt[(x - 1) * m + y] = n * m + 4;
		sz[n * m + 4]++;
	}
	else if(y == m){
		rt[(x - 1) * m + y] = n * m + 2;
		sz[n * m + 2]++;
	}
	else{
		rt[(x - 1) * m + y] = (x - 1) * m + y;
		sz[(x - 1) * m + y] = 1;
	}
	for(int i = 0; i < 8; i++){
		int tempx = x + xx[i], tempy = y + yy[i];
		if(!c[tempx][tempy]) continue;
		merge((tempx - 1) * m + tempy, (x - 1) * m + y);
	}
	c[x][y] = 1;
	return 1;
}

void process(){
	cin >> n >> m;
	for(int i = 1; i <= 4; i++){
		rt[n * m + i] = n * m + i;
	}
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			int x;
			cin >> x;
			if(x) upd(i, j);
		}
	}
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		cout << upd(x, y) << "\n";
	}
}

signed main(){
	ios_base::sync_with_stdio(0);
	process();
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 95