241312026-02-04 17:41:14algoproÚtépítéscpp17Time limit exceeded 95/100899ms2676 KiB
// UUID: 929ad834-1146-495e-8c1d-7356fd625052
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

vector<vector<int>> csucsok;
vector<bool> bejart;
vector<int> par;

int dfs(int akt){
	bejart[akt] = 1;

	for(int x : csucsok[akt]){
		if(par[x] == -1){
			par[x] = akt;
			return 1;
		} else{
			if(bejart[par[x]]) continue;

			assert(par[x] != akt);

			int a = dfs(par[x]);

			if(a){
				par[x] = akt;
				return 1;
			}
		}
	}

	return 0;
}

int main() {
	int n, m;
	cin >> n >> m;

	int ossz = (n+1)*(m+1);

	csucsok.assign(ossz, vector<int>());

	for(int i = 0; i < n; i++){
		string s;
		cin >> s;

		for(int j = 0; j < m; j++){
			int akt = i*(m+1) + j;

			if(s[j] == '/'){
				csucsok[akt + 1].push_back(akt + m + 1);
				csucsok[akt + m + 1].push_back(akt + 1);
			} else if(s[j] == '\\'){
				csucsok[akt].push_back(akt + m + 2);
				csucsok[akt + m + 2].push_back(akt);
			}
		}
	}

	for(auto &x : csucsok){
		random_shuffle(x.begin(), x.end());
	}

	par.assign(ossz, -1);


	int ans = 0;
	for(int i = 0; i < ossz; i++){
		if((i / (m+1)) % 2 == 1) continue;

		bejart.assign(ossz, 0);
		int a = dfs(i);
		ans += a;
	}

	cout << ans << "\n";

	vector<vector<int>> valasz(n+1, vector<int>(m+1, 0));

	for(int i = 1; i < n+1; i+= 2){
		for(int j = 0; j < m+1; j++){
			if(par[i*(m+1) + j] == -1) continue;

			int akt = i*(m+1) + j;
			int kovi = par[akt];

			if(kovi + m+2 == akt){
				valasz[i - 1][j - 1] = 1;
			} else if(kovi + m == akt){
				valasz[i - 1][j] = 2;
			} else if(akt + m == kovi){
				valasz[i][j - 1] = 2;
			} else if(akt + m+2 == kovi){
				valasz[i][j] = 1;
			} else{
				assert(0 == 1);
			}
		}
	}

	string s = ".\\/";

	for(int i = 0; i < n; i++){
		for(int j = 0; j < m; j++){
			cout << s[valasz[i][j]];
		}
		cout << "\n";
	}
}
SubtaskSumTestVerdictTimeMemory
base95/100
1Accepted0/01ms316 KiB
2Accepted0/012ms2612 KiB
3Accepted5/51ms316 KiB
4Accepted5/51ms316 KiB
5Accepted5/51ms316 KiB
6Accepted5/51ms316 KiB
7Accepted5/51ms316 KiB
8Accepted5/51ms508 KiB
9Accepted5/52ms316 KiB
10Accepted5/51ms508 KiB
11Accepted5/52ms316 KiB
12Accepted5/52ms316 KiB
13Accepted5/52ms316 KiB
14Accepted5/52ms564 KiB
15Accepted5/54ms820 KiB
16Accepted5/520ms2172 KiB
17Accepted5/58ms2236 KiB
18Time limit exceeded0/5899ms2060 KiB
19Accepted5/517ms2100 KiB
20Accepted5/514ms2644 KiB
21Accepted5/514ms2676 KiB
22Accepted5/5758ms2404 KiB