Submission #684966

#	Time	Username	Problem	Language	Result	Execution time	Memory
684966		NK_	Furniture (JOI20_furniture)	C++17	0 / 100	4 ms	468 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 HSH = [&](int r, int c) { return r * M + c; };

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

	DSU G, H, V; G.init(N * M + 5), H.init(N * M + 5), V.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) {
		auto it = S.upper_bound(x);
		if (it == end(S)) return -1;
		return *it;
	};

	auto less = [&](const set<int> &S, int x) {
		auto it = S.lower_bound(x);
		if (it == begin(S)) return -1;
		return *prev(it);
	};

	auto add = [&](int r, int c) -> array<int, 3> {
		int g = 0, h = 0, v = 0;
		if (!A[r][c]) return {0, 0, 0};

		// cout << "ADD: " << 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;

			G.unite(HSH(r, c), HSH(nr, nc)); ++g;
			H.unite(HSH(r, c), HSH(nr, nc)); ++h;
			V.unite(HSH(r, c), HSH(nr, nc)); ++v;

		}

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

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

		if (r-1 >= 0) {
			int cx = less(ROW[r-1], c);
			if (cx != -1) { 
				// cout << r-1 << " v " << cx << endl;
				++v; V.unite(HSH(r, c), HSH(r-1, cx)); 
			}
		}

		if (r+1 < N) {
			int cx = more(ROW[r+1], c);
			if (cx != -1) { 
				// cout << r+1 << " v " << cx << endl;
				++v; V.unite(HSH(r, c), HSH(r+1, cx));  
			}
		}

		if (r == 0) { 
			G.unite(HSH(r, c), U); ++g; 
			V.unite(HSH(r, c), U); ++v;
		}

		if (r == N-1) { 
			G.unite(HSH(r, c), D); ++g; 
			V.unite(HSH(r, c), D); ++v;
		}

		if (c == 0) { 
			G.unite(HSH(r, c), L); ++g; 
			H.unite(HSH(r, c), L); ++h;
		}

		if (c == M-1) { 
			G.unite(HSH(r, c), R); ++g; 
			H.unite(HSH(r, c), R); ++h;
		}

		return {g, h, v};
	};

	auto backup = [&](int g, int h, int v) {
		for(int i = 0; i < g; i++) G.rollback();
		for(int i = 0; i < h; i++) H.rollback();
		for(int i = 0; i < v; i++) V.rollback();
	};

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

	auto check = [&]() {
		// cout << H.sameSet(L, R) << V.sameSet(U, D) << G.sameSet(U, L) << G.sameSet(D, R) << endl;
		return !(H.sameSet(L, R) || V.sameSet(U, D) || G.sameSet(U, L) || G.sameSet(D, R));
	};
	
	// cout << check()<< endl << endl;
	int Q; cin >> Q;
	for(int q = 0; q < Q; q++) {
		int r, c; cin >> r >> c; --r, --c; A[r][c] = 1;
		auto [g, h, v] = add(r, c);

		int res = check();
		cout << res << nl;

		if (!res) { 
			A[r][c] = 0; 
			backup(g, h, v);
			ROW[r].erase(c); COL[c].erase(r);
		}
	}

    return 0;
}

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