241332026-02-04 17:46:45algoproÚtépítéscpp17Wrong answer 20/10012ms2996 KiB
// UUID: 970984e9-d2e1-45df-bdd7-225be2cdb780
#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast")

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

bool dfs(int akt){
	bejart[akt] = true;

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

			if(dfs(par[x])){
				par[x] = akt;
				bejart[akt] = false;
				return true;
			}
		}
	}

	bejart[akt] = false;

	return false;
}

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);
	bejart.assign(ossz, 0);


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

		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
base20/100
1Accepted0/01ms508 KiB
2Wrong answer0/09ms2612 KiB
3Accepted5/51ms316 KiB
4Wrong answer0/51ms316 KiB
5Wrong answer0/51ms316 KiB
6Accepted5/51ms500 KiB
7Wrong answer0/51ms316 KiB
8Wrong answer0/51ms316 KiB
9Wrong answer0/51ms316 KiB
10Wrong answer0/51ms316 KiB
11Wrong answer0/51ms500 KiB
12Wrong answer0/51ms316 KiB
13Wrong answer0/52ms564 KiB
14Accepted5/52ms564 KiB
15Wrong answer0/54ms820 KiB
16Wrong answer0/58ms2148 KiB
17Wrong answer0/57ms2328 KiB
18Accepted5/510ms2256 KiB
19Wrong answer0/58ms2356 KiB
20Wrong answer0/512ms2776 KiB
21Wrong answer0/510ms2996 KiB
22Wrong answer0/57ms2048 KiB