Submission #1304720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1304720		ToniB	T-Covering (eJOI19_covering)	C++20	55 / 100	63 ms	4852 KiB

covering

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

const int N = 1e6 + 2;

const int nxt_x[] = {1, 1, 0, -1};
const int nxt_y[] = {0, 1, 1, 1};

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

int n, m, K, ans_sum;
vector<int> a[N];
vector<bool> spec[N], marked[N];
bool ans = 1;

bool mark(int i, int j, int dir) {
	marked[i][j] = 1;
	ans_sum += a[i][j];
	for (int k = 0; k < 4; ++k) {
		if (k == dir) continue;
		if (i + dx[k] < 0 || i + dx[k] >= n || j + dy[k] < 0 || j + dy[k] >= m) return 0;
		if (marked[i + dx[k]][j + dy[k]]) return 0;
		marked[i + dx[k]][j + dy[k]] = 1;
		ans_sum += a[i + dx[k]][j + dy[k]];
	}
	
	return 1;
}

bool check(int i, int j) {
	if (!spec[i][j] || marked[i][j]) return 1;
	int bad = -1, cnt = 0;
	for (int k = 0; k < 4; ++k) {
		if (i + dx[k] < 0 || i + dx[k] >= n || j + dy[k] < 0 || j + dy[k] >= m) {
			bad = k; continue;
		}
		if (marked[i + dx[k]][j + dy[k]]) {
			bad = k; continue;
		}
		++cnt;
	}
	
	bool ret = 1;
	
	if (cnt < 3) return 0;
	if (cnt == 4) return 1;
	if (cnt == 3) ret &= mark(i, j, bad);

	for (int di = -2; di <= 2; ++di) {
		for (int dj = -2; dj <= 2; ++dj) {
			if (i + di < 0 || i + di >= n || j + dj < 0 || j + dj >= m) continue;
			ret &= check(i + di, j + dj);
		}
	}

	return ret;
}

void dfs(int i, int j, int& cycles, int& min_val, int prev_dir = -1) {
	ans_sum += a[i][j];
	for (int k = 0; k < 4; ++k) {
		min_val = min(min_val, a[i + dx[k]][j + dy[k]]);
		if (!marked[i + dx[k]][j + dy[k]]) {
			ans_sum += a[i + dx[k]][j + dy[k]];
		}
		marked[i + dx[k]][j + dy[k]] = 1;
	}
	marked[i][j] = 1;
	for (int k = 0; k < 4; ++k) {
		if (i + 2 * dx[k] < 0 || i + 2 * dx[k] >= n) continue;
		if (j + 2 * dy[k] < 0 || j + 2 * dy[k] >= m) continue;
		if (k == prev_dir) continue;
		
		if (!spec[i + 2 * dx[k]][j + 2 * dy[k]]) continue;
		
		if (marked[i + 2 * dx[k]][j + 2 * dy[k]]) cycles++;
		else {
			dfs(i + 2 * dx[k], j + 2 * dy[k], cycles, min_val, 2 ^ k);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	cin >> n >> m;
	
	for (int i = 0; i < n; ++i) {
		a[i].resize(m, 0);
		for (int& x : a[i]) cin >> x;
		
		spec[i].resize(m, 0);
		marked[i].resize(m, 0);
	}
	
	cin >> K;
	for (int i = 0; i < K; ++i) {
		int x, y;
		cin >> x >> y;
		spec[x][y] = 1;
	}
	
	for (int i = 0; i < n; ++i) {
		vector<int> which = {0, 1, 1, 2};
		for (int j = 0; j < m; ++j) {
			if (!spec[i][j]) continue;
			for (int k = 0; k < 4; ++k) {
				if (i + nxt_x[k] >= n || i + nxt_x[k] < 0 || j + nxt_y[k] >= m) continue;
				if (spec[i + nxt_x[k]][j + nxt_y[k]]) {
					ans &= !marked[i][j] && !marked[i + nxt_x[k]][j + nxt_y[k]];
					ans &= mark(i, j, which[k]);
					ans &= mark(i + nxt_x[k], j + nxt_y[k], 2 ^ which[k]);
				}
			}
		}
	}
	
	if (!ans) {
		cout << "No\n"; return 0;
	}

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			ans &= check(i, j);
		}
	}
	
	if (!ans) {
		cout << "No\n"; return 0;
	}
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			if (spec[i][j] && !marked[i][j]) {
				int cycles = 0, min_val = 1000;
				dfs(i, j, cycles, min_val);
				
				if (cycles > 1) ans = 0;
				if (!cycles) ans_sum -= min_val;
			}
		}
	}
	
	if (!ans) cout << "No\n";
	else cout << ans_sum << "\n";
	
	if (!ans) assert(0);

	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 0 / 15
• Subtask 6: 20 / 20
• Subtask 7: 0 / 30