9999 2024. 03. 23 20:37:30 111 Útépítés cpp17 Hibás válasz 38/100 878ms 11072 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

vector<int> kuhn(vector<vector<int>>& g, int n, int m) {
	vector<int> a(n), b(m, -1);
	auto dfs = [&](auto self, int i) {
		if (a[i]) {
			return 0;
		}
		a[i] = 1;
		for (int j : g[i]) {
			if (b[j] == -1 || self(self, b[j])) {
				b[j] = i;
				return 1;
			}
		}
		return 0;
	};
	for (int i = 0; i < n; i++) {
		fill(a.begin(), a.end(), 0);
		dfs(dfs, i);
	}
	return b;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<vector<int>>g((N+1)*(M+1));
	auto C=[&](int i, int j){
		return i*(M+1)+j;
	};
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			char c;
			cin>>c;
			if(c=='/'){
				if(i%2==0){
					g[C(i,j+1)].push_back(C(i+1,j));
				}
				else{
					g[C(i+1,j)].push_back(C(i,j+1));
				}
			}
			if(c=='\\'){
				if(i%2==0){
					g[C(i,j)].push_back(C(i+1,j+1));
				}
				else{
					g[C(i+1,j+1)].push_back(C(i,j));
				}
			}
		}
	}
	vector<vector<int>>a((N+2)/2*(M+1)),b((N+1)/2*(M+1));
	for(int i=0;i<N+1;i++){
		for(int j=0;j<M+1;j++){
			for(int o:g[C(i,j)]){
				int k=o/(M+1),l=o%(M+1);
				if(i%2==0){
					a[C(i/2,j)].push_back(C(k/2,l));
				}
				else {
					b[C(i/2,j)].push_back(C(k/2,l));
				}
			}
		}
	}
	auto x=kuhn(a,a.size(),b.size());
	cout<<b.size()-count(x.begin(),x.end(),-1)<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 38/100
1 Hibás válasz 0/0 3ms 2016 KiB
2 Hibás válasz 0/0 131ms 8772 KiB
3 Részben helyes 2/5 3ms 2244 KiB
4 Részben helyes 2/5 3ms 2472 KiB
5 Részben helyes 2/5 3ms 2684 KiB
6 Részben helyes 2/5 3ms 3152 KiB
7 Részben helyes 2/5 3ms 3104 KiB
8 Részben helyes 2/5 3ms 3220 KiB
9 Részben helyes 2/5 3ms 3212 KiB
10 Részben helyes 2/5 3ms 3268 KiB
11 Részben helyes 2/5 3ms 3840 KiB
12 Részben helyes 2/5 3ms 3972 KiB
13 Részben helyes 2/5 3ms 4020 KiB
14 Részben helyes 2/5 12ms 4628 KiB
15 Részben helyes 2/5 13ms 5284 KiB
16 Részben helyes 2/5 145ms 9308 KiB
17 Részben helyes 2/5 131ms 9264 KiB
18 Időlimit túllépés 0/5 878ms 6284 KiB
19 Részben helyes 2/5 135ms 9800 KiB
20 Részben helyes 2/5 136ms 11072 KiB
21 Részben helyes 2/5 133ms 11064 KiB
22 Részben helyes 2/5 584ms 10172 KiB