9998 2024. 03. 23 19:55:19 111 Útépítés cpp17 Hibás válasz 26/100 901ms 28156 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

int dinic(vector<unordered_map<int, int>>& g, int s, int t) {
	int flow = 0;
	bool cont = true;
	while (cont) {
		vector<int> lvl(g.size(), -1);
		vector<int> nxt[2];
		lvl[s] = 0;
		nxt[0].push_back(s);
		for (int i = 1; !nxt[i ^ 1].empty(); i ^= 1) {
			nxt[i].clear();
			for (int j : nxt[i ^ 1]) {
				for (auto p : g[j]) {
					if (lvl[p.first] == -1 && p.second > 0) {
						lvl[p.first] = lvl[j] + 1;
						nxt[i].push_back(p.first);
					}
				}
			}
		}
		cont = false;
		while (true) {
			vector<int> vis(g.size());
			vector<int> pth;
			auto dfs = [&](auto dfs, int i) {
				if (i == t) {
					return true;
				}
				for (auto p : g[i]) {
					if (!vis[p.first] && lvl[p.first] == lvl[i] + 1 && p.second > 0) {
						vis[p.first] = true;
						pth.push_back(p.first);
						if (dfs(dfs, p.first)) {
							return true;
						}
						pth.pop_back();
					}
				}
				return false;
			};
			if (!dfs(dfs, s)) {
				break;
			}
			int bottleneck = LLONG_MAX;
			int i = s;
			for (int j : pth) {
				bottleneck = min(bottleneck, g[i][j]);
				i = j;
			}
			i = s;
			for (int j : pth) {
				g[i][j] -= bottleneck;
				g[j][i] += bottleneck;
				i = j;
			}
			flow += bottleneck;
			cont = true;
		}
	}
	return flow;
}

int mbm(vector<vector<int>>&g){
	vector<unordered_map<int,int>>gg(g.size());
	for(int i=0;i<g.size();i++){
		for(int j:g[i]){
			gg[i][j]=1;
		}
	}
	return dinic(gg,0,1);
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N,M;
	cin>>N>>M;
	vector<vector<int>>g(2+(N+1)*(M+1));
	auto C=[&](int i, int j){
		return 2+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));
				}
			}
		}
	}
	for(int i=0;i<N+1;i++){
		for(int j=0;j<M+1;j++){
			if(i%2==0){
				g[0].push_back(C(i,j));
			}
			else{
				g[C(i,j)].push_back(1);
			}
		}
	}
	cout<<mbm(g)<<'\n';
	return 0;
}
Részfeladat Összpont Teszt Verdikt Idő Memória
base 26/100
1 Hibás válasz 0/0 3ms 1832 KiB
2 Időlimit túllépés 0/0 901ms 13764 KiB
3 Részben helyes 2/5 3ms 2548 KiB
4 Részben helyes 2/5 3ms 2648 KiB
5 Részben helyes 2/5 3ms 2616 KiB
6 Részben helyes 2/5 4ms 3528 KiB
7 Részben helyes 2/5 3ms 2880 KiB
8 Részben helyes 2/5 3ms 3176 KiB
9 Részben helyes 2/5 3ms 3580 KiB
10 Részben helyes 2/5 3ms 3456 KiB
11 Részben helyes 2/5 13ms 4964 KiB
12 Részben helyes 2/5 10ms 4796 KiB
13 Részben helyes 2/5 14ms 4912 KiB
14 Részben helyes 2/5 17ms 7944 KiB
15 Részben helyes 2/5 197ms 10592 KiB
16 Időlimit túllépés 0/5 837ms 14184 KiB
17 Időlimit túllépés 0/5 850ms 14460 KiB
18 Időlimit túllépés 0/5 859ms 28156 KiB
19 Időlimit túllépés 0/5 885ms 14684 KiB
20 Időlimit túllépés 0/5 860ms 16628 KiB
21 Időlimit túllépés 0/5 875ms 16612 KiB
22 Időlimit túllépés 0/5 865ms 14648 KiB