99982024-03-23 19:55:19111Útépítéscpp17Wrong answer 26/100901ms28156 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;
}
SubtaskSumTestVerdictTimeMemory
base26/100
1Wrong answer0/03ms1832 KiB
2Time limit exceeded0/0901ms13764 KiB
3Partially correct2/53ms2548 KiB
4Partially correct2/53ms2648 KiB
5Partially correct2/53ms2616 KiB
6Partially correct2/54ms3528 KiB
7Partially correct2/53ms2880 KiB
8Partially correct2/53ms3176 KiB
9Partially correct2/53ms3580 KiB
10Partially correct2/53ms3456 KiB
11Partially correct2/513ms4964 KiB
12Partially correct2/510ms4796 KiB
13Partially correct2/514ms4912 KiB
14Partially correct2/517ms7944 KiB
15Partially correct2/5197ms10592 KiB
16Time limit exceeded0/5837ms14184 KiB
17Time limit exceeded0/5850ms14460 KiB
18Time limit exceeded0/5859ms28156 KiB
19Time limit exceeded0/5885ms14684 KiB
20Time limit exceeded0/5860ms16628 KiB
21Time limit exceeded0/5875ms16612 KiB
22Time limit exceeded0/5865ms14648 KiB