240352026-02-03 18:10:18algoproÚtépítéscpp17Wrong answer 2/100899ms2612 KiB
// UUID: b76d830f-1646-48d4-9847-ff0d3c216424
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> nbrs;
vector<int> mt;
vector<bool> vis;

bool kuhn(int Indx){
	if(vis[Indx]) return false;
	vis[Indx]=true;
	for(int x : nbrs[Indx]){
		if(mt[x]==-1 || kuhn(mt[x])){
			mt[x]=Indx;
			return true;
		}
	}
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int width, height;
	cin >> width >> height;
	int n=(width+1)*(height+1);
	nbrs.resize(n);
	mt.resize(n, -1);
	vector<bool> mtd(n, false);
	for(int i=0;i<width;i++){
		string s; cin >> s;
		for(int j=0;j<height;j++){
			if(s[j]=='\\'){
				int u=i*(height+1)+j, v=(i+1)*(height+1)+(j+1);
				nbrs[u].push_back(v); nbrs[v].push_back(u);
				if(i%2!=0 && -1==mt[u] && !mtd[v]){
					mt[u]=v;
					mtd[v]=true;
				}
				if((i+1)%2!=0 && -1==mt[v] && !mtd[u]){
					mt[v]=u;
					mtd[u]=true;
				}
			}
			if(s[j]=='/'){
				int u=(i+1)*(height+1)+j, v=i*(height+1)+(j+1);
				nbrs[u].push_back(v); nbrs[v].push_back(u);
				if((i+1)%2!=0 && -1==mt[u] && !mtd[v]){
					mt[u]=v;
					mtd[v]=true;
				}
				if(i%2!=0 && -1==mt[v] && !mtd[u]){
					mt[v]=u;
					mtd[u]=true;
				}
			}
		}
	}
	for(int i=0;i<n;i++) random_shuffle(nbrs[i].begin(), nbrs[i].end());
	for(int i=0;i<n;i++){
		if((i/(height+1))%2==0){
			vis.assign(n, false);
			kuhn(i);
		}
	}
	int cnt=0;
	for(int i=0;i<n;i++) cnt+=(-1!=mt[i]);
	cout << cnt;
	for(int i=0;i<width;i++){
		cout << '\n';
		for(int j=0;j<height;j++){
			int u=i*(height+1)+j;
			if(mt[u]==u+height+2 || u==mt[u+height+2]) cout << '\\';
			else if(mt[u+1]==u+height+1 || u+1==mt[u+height+1]) cout << '/';
			else cout << '.';
		}
	}
}
SubtaskSumTestVerdictTimeMemory
base2/100
1Accepted0/01ms316 KiB
2Wrong answer0/010ms2356 KiB
3Wrong answer0/51ms316 KiB
4Wrong answer0/51ms508 KiB
5Wrong answer0/51ms316 KiB
6Partially correct2/51ms316 KiB
7Wrong answer0/51ms316 KiB
8Wrong answer0/51ms316 KiB
9Wrong answer0/51ms500 KiB
10Wrong answer0/51ms316 KiB
11Wrong answer0/52ms316 KiB
12Wrong answer0/52ms484 KiB
13Wrong answer0/52ms564 KiB
14Wrong answer0/52ms564 KiB
15Wrong answer0/54ms820 KiB
16Time limit exceeded0/5898ms2484 KiB
17Time limit exceeded0/5899ms2452 KiB
18Time limit exceeded0/5899ms2100 KiB
19Wrong answer0/523ms2188 KiB
20Wrong answer0/514ms2612 KiB
21Wrong answer0/516ms2612 KiB
22Time limit exceeded0/5879ms2116 KiB