240402026-02-03 18:20:51algoproÚtépítéscpp17Time limit exceeded 90/100898ms5184 KiB
// UUID: b1c5c126-e6f6-42b1-975a-9c59fcf7498c
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> g;
map<int,map<int,int>> g2;
map<int,int> pr, used;

bool dfs(int p) {
	if (used[p] == 1) return false;
	used[p] = 1;
	for (int p2 : g[p]) {
		if (pr[p2] == 0 || dfs(pr[p2])) {
			pr[p2] = p;
			return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	int n, m; cin >> n >> m;

	g.resize((n+1)*(m+1)+1);

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char c; cin >> c;
			if (c == '.') continue;
			if (c == '\\') {
				g[(i-1)*(m+1) + j].push_back(i*(m+1) + j+1);
				g[i*(m+1) + j+1].push_back((i-1)*(m+1) + j);
			} else {
				g[(i-1)*(m+1) + j+1].push_back(i*(m+1) + j);
				g[i*(m+1) + j].push_back((i-1)*(m+1) + j+1);
			}
		}
	}

	for (int i = 1; i <= (n+1)*(m+1); i++) {
		if (((i + m) / (m+1)) % 2) {
			dfs(i);
			used.clear();
		}
	}

	int ans = 0;

	for (auto i : pr) {
		if (i.second != 0) {
			int a = i.first, b = i.second;
			if (a > b) swap(a, b);
			if (b - a == m+2) {
				g2[(m + a) / (m+1)][a - ((m + a) / (m+1) - 1)*(m+1)] = 1;
			}
			if (b - a == m) {
				g2[(m + a) / (m+1)][a - ((m + a) / (m+1) - 1)*(m+1) - 1] = 2;
			}
			ans++;
		}
	}

	cout << ans << '\n';

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (g2[i][j] == 1) cout << '\\';
			else
			if (g2[i][j] == 2) cout << '/';
			else
			cout << '.';
		}
		cout << '\n';
	}

	return 0;
}
SubtaskSumTestVerdictTimeMemory
base90/100
1Accepted0/01ms316 KiB
2Accepted0/029ms4912 KiB
3Accepted5/51ms512 KiB
4Accepted5/51ms316 KiB
5Accepted5/51ms316 KiB
6Accepted5/51ms564 KiB
7Accepted5/51ms316 KiB
8Accepted5/52ms316 KiB
9Accepted5/52ms316 KiB
10Accepted5/52ms316 KiB
11Accepted5/53ms564 KiB
12Accepted5/53ms564 KiB
13Accepted5/54ms564 KiB
14Accepted5/54ms1192 KiB
15Accepted5/510ms1584 KiB
16Accepted5/5397ms4188 KiB
17Accepted5/520ms4204 KiB
18Time limit exceeded0/5898ms2060 KiB
19Accepted5/5160ms4092 KiB
20Accepted5/543ms5184 KiB
21Accepted5/543ms5172 KiB
22Time limit exceeded0/5884ms2236 KiB