제출 #684963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684963		NK_	Furniture (JOI20_furniture)	C++17	0 / 100	1 ms	340 KiB

furniture

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

struct DSU {
	vector<int> e; void init(int n) { e = vector<int>(n, -1); }
	int get(int x) { return e[x] < 0 ? x : get(e[x]); }
	int sameSet(int x, int y) { return get(x) == get(y); }
	vector<array<int, 4>> R;
	bool unite(int x, int y) {
		x = get(x), y = get(y); if (x == y) {
			R.push_back({-1, -1, -1, -1});
			return 0;
		}
		if (e[x] > e[y]) swap(x, y);
		R.push_back({x, e[x], y, e[y]});
		e[x] += e[y]; e[y] = x; return 1;
	}
	void rollback() {
		if (size(R) == 0) return;
		auto [x, ex, y, ey] = R.back(); R.pop_back();
		if (x == -1) return;
		e[x] = ex, e[y] = ey;
	}
};

int dx[8] = {1, 1, 1, 0, 0, -1, -1, -1};
int dy[8] = {1, 0, -1, 1, -1, 1, 0, -1};

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M; cin >> N >> M;

	auto H = [&](int r, int c) { return r * M + c; };

	vector<vector<int>> A(N, vector<int>(M));

	DSU d; d.init(N * M + 5);

	const int U = N * M, D = N * M + 1, L = N * M + 2, R = N * M + 3;

	vector<set<int>> ROW(N), COL(M);

	auto more = [&](const set<int> &S, int x) {
		// cout << "MORE: ";
		// for(auto y : S) cout << y << " ";
		// cout << "X: " << x << endl;
		auto it = S.upper_bound(x);
		if (it == end(S)) return -1;
		return *it;
	};

	auto less = [&](const set<int> &S, int x) {
		// cout << "LESS: ";
		// for(auto y : S) cout << y << " ";
		// cout << "X: " << x << endl;
		auto it = S.lower_bound(x);
		if (it == begin(S)) return -1;
		return *prev(it);
	};

	auto add = [&](int r, int c) {
		int E = 0;
		if (!A[r][c]) return E;

		// cout << "ADD: " << endl;
		// cout << r << " " << c << endl;

		ROW[r].insert(c); COL[c].insert(r);

		for(int dir = 0; dir < 8; dir++) {

			int nr = dx[dir] + r, nc = dy[dir] + c;
			if (nr < 0 || nc < 0 || nr >= N || nc >= M) continue;
			if (!A[nr][nc]) continue;

			// cout << nr << " " << nc << endl;

			d.unite(H(r, c), H(nr, nc)); ++E;
		}

		for(int cx = c; cx >= max(c-1, 0); cx--) { 
			int rx = less(COL[cx], r);
			if (rx != -1) { 
				// cout << rx << " " << cx << endl;
				++E; d.unite(H(r, c), H(rx, cx)); 
			}
		}

		for(int cx = c; cx <= min(c+1, M-1); cx++) { 
			int rx = more(COL[cx], r);
			if (rx != -1) {
				// cout << rx << " " << cx << endl;
				++E; d.unite(H(r, c), H(rx, cx)); 
			}
		}

		for(int rx = r; rx >= max(r-1, 0); rx--) {
			int cx = less(ROW[rx], c);
			if (cx != -1) { 
				// cout << rx << " " << cx << endl;
				++E; d.unite(H(r, c), H(rx, cx)); 
			}
		}

		for(int rx = r; rx <= min(r+1, N-1); rx++) {
			int cx = more(ROW[rx], c);
			if (cx != -1) { 
				// cout << rx << " " << cx << endl;
				++E; d.unite(H(r, c), H(rx, cx)); 
			}
		}

		if (r == 0) { d.unite(H(r, c), U); ++E; }

		if (r == N-1) { d.unite(H(r, c), D); ++E; }

		if (c == 0) { d.unite(H(r, c), L); ++E; }

		if (c == M-1) { d.unite(H(r, c), R); ++E; }

		return E;
	};

	for(int r = 0; r < N; r++) {
		for(int c = 0; c < M; c++) {
			cin >> A[r][c];
			add(r, c);
		}
	}


	auto check = [&]() {
		for(auto x : {L, D}) for(auto y : {U, R}) if (d.sameSet(x, y)) return 0;
		return 1;
	};
	
	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int r, c; cin >> r >> c; --r, --c; A[r][c] = 1;
		int e = add(r, c); 
		int res = check();
		// cout << "ANS: ";
		cout << res << nl;

		if (!res) { 
			A[r][c] = 0; 
			for(int _ = 0; _ < e; _++) d.rollback(); 
			ROW[r].erase(c); COL[c].erase(r);
		}
	}

    return 0;
}

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