oj.uz

답안 #1031783

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1031783 2024-07-23T07:09:08 Z 정민찬(#10962) Furniture (JOI20_furniture) C++17
5 / 100
 5000 ms 75140 KB 
#include <bits/stdc++.h>

using namespace std;

vector<int> g[1000010];
int par[1000010];
int l[1000010], r[1000010];

int Find(int x) {
	if (par[x] == x) return x;
	return par[x] = Find(par[x]);
}

void update_l(int x, int y);
void update_r(int x, int y);

int n, m;

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	if (x == y) return;
	if (l[x] && !l[y]) {
		for (auto &i : g[y]) update_l(i/m+1, i%m+1);
	}
	if (!l[x] && l[y]) {
		for (auto &i : g[x]) update_l(i/m+1, i%m+1);
	}
	if (r[x] && !r[y]) {
		for (auto &i : g[y]) update_r(i/m+1, i%m+1);
	}
	if (!r[x] && r[y]) {
		for (auto &i : g[x]) update_r(i/m+1, i%m+1);
	}
	if (g[x].size() < g[y].size()) swap(x, y);
	for (auto &i : g[y]) g[x].push_back(i);
	l[x] |= l[y];
	r[x] |= r[y];
	par[y] = x;
	//assert(!l[x] || !r[x]);
}

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

int le[1010], re[1010];
int C[1010][1010];

bool Check(int x, int y) {
	if (C[x][y]) return true;
	bool lf = false, rf = false;
	if (x == n || y == 1) lf = true;
	if (x == 1 || y == m) rf = true;
	for (int k=0; k<8; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (!C[nx][ny]) continue;
		int p = Find((nx-1) * m + ny-1);
		if (l[p]) lf = true;
		if (r[p]) rf = true;
	}
	if (lf && rf) return false;
	return true;
}

int dp[110][110];

bool Check2() {
    memset(dp, 0, sizeof(dp));
    dp[1][1] = 1;
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=m; j++) {
            if (C[i][j]) continue;
            dp[i][j] |= dp[i-1][j];
            dp[i][j] |= dp[i][j-1];
        }
    }
    return dp[n][m];
}

void Update(int x, int y) {
	assert(C[x][y] == 0);
	C[x][y] = 1;
	int p = Find((x-1) * m + y - 1);
	assert(p == (x-1) * m + y - 1);
	if (x == n || y == 1) l[p] = 1, update_l(x, y);
	if (x == 1 || y == m) r[p] = 1, update_r(x, y);
	for (int k=0; k<8; k++) {
		int nx = x + dx[k];
		int ny = y + dy[k];
		if (C[nx][ny] == 1) {
			Union((nx-1) * m + ny-1, (x-1) * m + y-1);
		}
	}
}

vector<pair<int,int>> st;

void update_l(int x, int y) {
	for (int i=x; i<=n; i++) {
		if (le[i] >= y) break;
		for (int j=y; j>le[i]; j--) {
			if (!C[i][j]) {
				st.push_back({i, j});
			}
		}
		le[i] = y;
	}
}

void update_r(int x, int y) {
	for (int i=x; i>=1; i--) {
		if (re[i] <= y) break;
		for (int j=y; j<re[i]; j++) {
			if (!C[i][j]) {
				st.push_back({i, j});
			}
		}
		re[i] = y;
	}
}

void cl_st() {
	while (!st.empty()) {
		int x = st.back().first;
		int y = st.back().second;
		st.pop_back();
		if (!C[x][y]) Update(x, y);
	}
}

int T[1010][1010];

int main() {
	ios_base :: sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			int num = (i-1)*m + j-1;
			g[num].push_back(num);
			par[num] = num;
		}
	}
	for (int i=1; i<=n; i++) {
		re[i] = m + 1;
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			cin >> T[i][j];
		}
	}
	for (int i=1; i<=n; i++) {
		for (int j=1; j<=m; j++) {
			if (!C[i][j] && T[i][j]) {
				st.push_back({i, j});
				cl_st();
			}
		}
	}
	int q;
	cin >> q;
	while (q --) {
		int x, y;
		cin >> x >> y;
		if (C[x][y] == 1) {
			cout << "1\n";
			continue;
		}
		bool ret = Check(x, y);
		C[x][y] = 1;
		bool ret2 = Check2();
		C[x][y] = 0;
		if (ret && !ret2) {
			for (int i=1; i<=n; i++) {
				cout << ">>";
				for (int j=1; j<=m; j++) {
					cout << C[i][j] << ' ';
				}
				cout << '\n';
			}
			return 0;
		}
		cout << ret << '\n';
		if (ret) {
			st.push_back({x, y});
			cl_st();
		}
	}
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24668 KB Output is correct
2 Correct 17 ms 24924 KB Output is correct
3 Correct 20 ms 25188 KB Output is correct
4 Correct 26 ms 25180 KB Output is correct
5 Correct 28 ms 25180 KB Output is correct
6 Correct 53 ms 25248 KB Output is correct
7 Correct 21 ms 25432 KB Output is correct
8 Correct 22 ms 25436 KB Output is correct
9 Correct 28 ms 25436 KB Output is correct

Subtask #2
0.0 / 95.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 24668 KB Output is correct
2 Correct 17 ms 24924 KB Output is correct
3 Correct 20 ms 25188 KB Output is correct
4 Correct 26 ms 25180 KB Output is correct
5 Correct 28 ms 25180 KB Output is correct
6 Correct 53 ms 25248 KB Output is correct
7 Correct 21 ms 25432 KB Output is correct
8 Correct 22 ms 25436 KB Output is correct
9 Correct 28 ms 25436 KB Output is correct
10 Correct 52 ms 27484 KB Output is correct
11 Correct 24 ms 24924 KB Output is correct
12 Execution timed out 5084 ms 75140 KB Time limit exceeded
13 Halted 0 ms 0 KB -