Submission #1171814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1171814		xnqs	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	130 ms	327680 KiB

dango_maker

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <functional>

int gs_left, gs_right;
int x, y;
char arr[3005][3005];
std::vector<bool> real_node;
std::vector<char> color;
std::vector<std::vector<int>> adj_list;

int Not(int node) {
	return ((node < x*y) ? node+x*y : node-x*y);
}

inline bool ok_line(int i, int j) {
	return arr[i][j] == 'R' && arr[i][j+1] == 'G' && arr[i][j+2] == 'W';
}

inline bool ok_column(int i, int j) {
	return arr[i][j] == 'R' && arr[i+1][j] == 'G' && arr[i+2][j] == 'W';
}

void dfs(int k, int c) {
	color[k] = c;
	for (const auto& i : adj_list[k]) {
		if (color[i]==-1) {
			dfs(i, c^1);
		}
		else {
			if (color[i]==color[k]) {
				exit(1);
			}
		}
	}
}

void build_graph() {
	for (int i = 0; i < x; i++) {
		for (int j = 0; j+2 < y; j++) {
			if (ok_line(i,j)) {
				real_node[i*y+j] = 1;
				if (i+2 < x && ok_column(i,j)) {
					adj_list[i*y+j].emplace_back(Not(i*y+j));
				}
				if (i-1 >= 0 && i+1 < x && ok_column(i-1,j+1)) {
					adj_list[i*y+j].emplace_back(Not((i-1)*y+j+1));
				}
				if (i-2 >= 0 && ok_column(i-2,j+2)) {
					adj_list[i*y+j].emplace_back(Not((i-2)*y+j+2));
				}
			}
		}
	}
	for (int i = 0; i+2 < x; i++) {
		for (int j = 0; j < y; j++) {
			if (ok_column(i,j)) {
				real_node[Not(i*y+j)] = 1;
				if (j+2 < y && ok_line(i,j)) {
					adj_list[Not(i*y+j)].emplace_back(i*y+j);
				}
				if (j-1 >= 0 && j+1 < y && ok_line(i+1,j-1)) {
					adj_list[Not(i*y+j)].emplace_back((i+1)*y+j-1);
				}
				if (j-2 >= 0 && ok_line(i+2,j-2)) {
					adj_list[Not(i*y+j)].emplace_back((i+2)*y+j-2);
				}
			}
		}
	}

	for (int i = 0; i < 2*x*y; i++) {
		if (real_node[i]&&color[i]==-1) {
			dfs(i, 0);
		}
	}
}

void normalize_graph() {
	std::unordered_map<int,int> norm_l;
	for (int i = 0; i < 2*x*y; i++) {
		if (real_node[i]&&color[i]==0) {
			norm_l[i] = 0;
		}
	}

	for (auto& i : norm_l) {
		i.second = ++gs_left;
	}

	std::unordered_map<int,int> norm_r;
	for (int i = 0; i < 2*x*y; i++) {
		if (real_node[i]&&color[i]==1) {
			norm_r[i] = 0;
		}
	}
	
	for (auto& i : norm_r) {
		i.second = ++gs_right;
	}

	//std::cout << gs_left << " " << gs_right << "\n";

	std::vector<std::vector<int>> new_adj(std::max(gs_left, gs_right)+1);
	for (int i = 0; i < 2*x*y; i++) {
		if (real_node[i]&&color[i]==0) {
			for (const auto& j : adj_list[i]) {
				//std::cout << norm[i] << " " << norm[j] << "\n";
				new_adj[norm_l[i]].emplace_back(norm_r[j]);
			}
		}
	}

	adj_list = new_adj;
}

void max_bipartite_matching() {
	std::vector<int> match_left(6000005, -1);
	std::vector<int> match_right(6000005, -1);
	std::vector<char> vis(6000005, 0);

	const std::function<bool(int)> dfs = [&](int k) {
		if (vis[k]) {
			return false;
		}

		vis[k] = 1;
		for (const auto& i : adj_list[k]) {
			if (match_right[i] == -1 || dfs(match_right[i])) {
				match_left[k] = i;
				match_right[i] = k;
				return true;
			}
		}
		
		return false;
	};

	while (1) {
		std::fill(vis.begin(), vis.end(), 0);
		bool done = 1;
		for (int i = 1; i <= gs_left; i++) {
			if (match_left[i] == -1) {
				done &= !dfs(i);
			}
		}

		if (done) {
			break;
		}
	}

	int ret = 0;
	for (int i = 1; i <= gs_left; i++) {
		ret += (match_left[i]!=-1);
	}
	
	//std::cout << ret << "\n";
	std::cout << gs_left + gs_right - ret << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> x >> y;
	adj_list.resize(2*x*y);
	real_node.assign(2*x*y,0);
	color.assign(2*x*y,-1);
	for (int i = 0; i < x; i++) {
		std::cin >> arr[i];
	}

	build_graph();
	normalize_graph();
	max_bipartite_matching();
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67