Submission #306233


Source Code Expand

#include <algorithm>
#include <functional>
#include <iostream>
#include <limits>
#include <queue>
#include <string>
#include <type_traits>
#include <utility>
#include <vector>
namespace lc {
template <class WeightType, class CapacityType>
struct EdgeWithWeightAndCapacity {
	int to;
	WeightType weight;
	CapacityType capacity;
	EdgeWithWeightAndCapacity() : to(0), weight(), capacity() { }
	EdgeWithWeightAndCapacity(
		int to, const WeightType &weight, const CapacityType &capacity)
		: to(to), weight(weight), capacity(capacity)
	{ }
};
}
namespace lc {
template <typename EdgeType>
class AdjacencyList {
public:
	typedef std::vector<EdgeType> ListType;
private:
	std::vector<ListType> m_lists;
public:
	explicit AdjacencyList(int n = 0)
		: m_lists(n)
	{ }
	int size() const { return m_lists.size(); }
	template <typename... Args>
	void add_edge(int u, Args&&... args){
		m_lists[u].emplace_back(args...);
	}
	const ListType &operator[](int u) const { return m_lists[u]; }
	ListType &operator[](int u){ return m_lists[u]; }
};
}
namespace lc {
template <class EdgeType>
struct ResidualEdge : public EdgeType {
	typedef ResidualEdge<EdgeType> self_type;
	int rev;
	ResidualEdge() : EdgeType(), rev(0) { }
	template <class... Args>
	ResidualEdge(int rev, Args&&... args)
		: EdgeType(args...)
		, rev(rev)
	{ }
	explicit ResidualEdge(const EdgeType &e)
		: EdgeType(e)
		, rev(0)
	{ }
};
template <class EdgeType>
class ResidualAdjacencyList
	: public AdjacencyList<ResidualEdge<EdgeType>>
{
public:
	explicit ResidualAdjacencyList(int n = 0)
		: AdjacencyList<ResidualEdge<EdgeType>>(n)
	{ }
};
template <class EdgeType>
auto make_residual(const AdjacencyList<EdgeType> &graph)
	-> ResidualAdjacencyList<EdgeType>
{
	typedef decltype(EdgeType().capacity) capacity_type;
	const int n = graph.size();
	ResidualAdjacencyList<EdgeType> result(n);
	for(int u = 0; u < n; ++u){
		for(const auto &e : graph[u]){
			const int v = e.to;
			const int rev_u = result[v].size();
			const int rev_v = result[u].size();
			result[u].emplace_back(rev_u, e);
			result[v].emplace_back(rev_v, e);
			result[v].back().to = u;
			result[v].back().capacity = capacity_type();
			result[v].back().weight = -e.weight;
		}
	}
	return result;
}
}
namespace lc {
template <class EdgeType>
auto mincostflow_primal_dual(
	int source, int sink, decltype(EdgeType().capacity) flow,
	ResidualAdjacencyList<EdgeType> &graph)
	-> decltype(EdgeType().weight)
{
	typedef decltype(EdgeType().weight) weight_type;
	typedef decltype(EdgeType().capacity) capacity_type;
	typedef std::pair<weight_type, int> weighted_pair;
	const weight_type inf = std::numeric_limits<weight_type>::max();
	const int n = graph.size();
	weight_type result = 0;
	std::vector<weight_type> h(n);
	std::vector<int> prev_vertex(n), prev_edge(n);
	while(flow > 0){
		std::priority_queue<
			weighted_pair, std::vector<weighted_pair>,
			std::greater<weighted_pair>> pq;
		std::vector<weight_type> dist(n, inf);
		dist[source] = weight_type();
		pq.push(std::make_pair(dist[source], source));
		while(!pq.empty()){
			weighted_pair p = pq.top();
			pq.pop();
			const int u = p.second;
			if(dist[u] < p.first){ continue; }
			for(size_t i = 0; i < graph[u].size(); ++i){
				const auto &e = graph[u][i];
				if(e.capacity <= 0){ continue; }
				const int v = e.to;
				const auto new_dist = dist[u] + e.weight + h[u] - h[v];
				if(dist[v] <= new_dist){ continue; }
				dist[v] = new_dist;
				prev_vertex[v] = u;
				prev_edge[v] = i;
				pq.push(std::make_pair(new_dist, v));
			}
		}
		if(dist[sink] >= inf){ return -1; }
		for(int i = 0; i < n; ++i){ h[i] += dist[i]; }
		weight_type diff = flow;
		for(int v = sink; v != source; v = prev_vertex[v]){
			diff = std::min(
				diff, graph[prev_vertex[v]][prev_edge[v]].capacity);
		}
		flow -= diff;
		result += diff * h[sink];
		for(int v = sink; v != source; v = prev_vertex[v]){
			auto &e = graph[prev_vertex[v]][prev_edge[v]];
			e.capacity -= diff;
			graph[v][e.rev].capacity += diff;
		}
	}
	return result;
}
}
using namespace std;
typedef lc::EdgeWithWeightAndCapacity<int, int> Edge;
typedef pair<int, int> pii;
static const int dx[] = { 1, 0, -1, 0 };
static const int dy[] = { 0, -1, 0, 1 };
static const int INF = 1000000000;
inline bool between(int a, int b, int c){
	return a <= b && b < c;
}
template <class EdgeType>
void solve(
	vector<string> &field, int s, int c,
	const lc::AdjacencyList<EdgeType> &graph)
{
	const int n = graph.size();
	const int h = field.size(), w = field[0].size();
	while(s < n - 2){
		bool flag = false;
		if(s >= w * h){
			s -= w * h;
			flag = true;
		}else{
			for(const auto &e : graph[s]){
				if(e.to >= n - 2){ continue; }
				if(e.to == s + w * h){ continue; }
				if(graph[e.to][e.rev].capacity == 0){
					s = e.to;
					flag = true;
					break;
				}
			}
		}
		if(!flag){ break; }
		const int y = s / w % h, x = s % w;
		if(field[y][x] == '.'){ field[y][x] = c; }
	}
}
int main(){
	ios_base::sync_with_stdio(false);
	int h, w;
	cin >> h >> w;
	vector<string> field(h);
	for(int i = 0; i < h; ++i){ cin >> field[i]; }
	const int num_vertices = h * w * 2 + 2;
	const int source = num_vertices - 2, sink = num_vertices - 1;
	int start = 0, goal_a = 0, goal_b = 0;
	lc::AdjacencyList<Edge> graph(num_vertices);
	for(int i = 0; i < h; ++i){
		for(int j = 0; j < w; ++j){
			const int x = i * w + j, y = x + w * h;
			if(field[i][j] == '#'){ continue; }
			graph.add_edge(x, y, 1, 1);
			if(field[i][j] == 'S'){
				start = x;
				graph.add_edge(source, y, 0, 2);
			}else if(field[i][j] == 'A'){
				goal_a = x;
				graph.add_edge(y, sink, 0, 1);
			}else if(field[i][j] == 'B'){
				goal_b = x;
				graph.add_edge(y, sink, 0, 1);
			}
			for(int d = 0; d < 4; ++d){
				const int nx = j + dx[d], ny = i + dy[d];
				if(!between(0, nx, w) || !between(0, ny, h)){ continue; }
				if(field[ny][nx] == 'O'){ continue; }
				graph.add_edge(y, nx + ny * w, 0, 1);
			}
		}
	}
	vector< vector<int> > dist(h, vector<int>(w, INF));
	queue<pii> q;
	q.push(pii(start / w, start % w));
	dist[start / w][start % w] = 0;
	while(!q.empty()){
		const pii p = q.front();
		q.pop();
		for(int d = 0; d < 4; ++d){
			const int nx = p.second + dx[d], ny = p.first + dy[d];
			if(!between(0, nx, w) || !between(0, ny, h)){ continue; }
			if(field[ny][nx] == '#'){ continue; }
			if(dist[ny][nx] >= INF){
				dist[ny][nx] = dist[p.first][p.second] + 1;
				q.push(pii(ny, nx));
			}
		}
	}
	auto residual = lc::make_residual(graph);
	const int cost = lc::mincostflow_primal_dual(source, sink, 2, residual);
	if(cost < 0 || cost > dist[goal_a / w][goal_a % w] + dist[goal_b / w][goal_b % w]){
		cout << "NA" << endl;
		return 0;
	}
	solve(field, goal_a, 'a', residual);
	solve(field, goal_b, 'b', residual);
	for(int i = 0; i < h; ++i){ cout << field[i] << endl; }
	return 0;
}

Submission Info

Submission Time
Task D - Maze
User logicmachine
Language C++11 (GCC 4.8.1)
Score 100
Code Size 7043 Byte
Status AC
Exec Time 33 ms
Memory 2204 KB

Judge Result

Set Name all
Score / Max Score 100 / 100
Status
AC × 41
Set Name Test Cases
all manual_j1.txt, manual_j10.txt, manual_j11.txt, manual_j12.txt, manual_j13.txt, manual_j14.txt, manual_j15.txt, manual_j2.txt, manual_j3.txt, manual_j4.txt, manual_j5.txt, manual_j6.txt, manual_j7.txt, manual_j8.txt, manual_j9.txt, manual_k1.txt, manual_k2.txt, random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_max_01.txt, random_max_02.txt, random_max_03.txt, random_max_04.txt, random_max_05.txt, random_max_06.txt, random_max_07.txt, random_max_08.txt, random_max_09.txt, random_max_10.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, white_01.txt, white_02.txt, white_03.txt, white_04.txt
Case Name Status Exec Time Memory
manual_j1.txt AC 25 ms 928 KB
manual_j10.txt AC 23 ms 928 KB
manual_j11.txt AC 31 ms 1956 KB
manual_j12.txt AC 23 ms 800 KB
manual_j13.txt AC 23 ms 804 KB
manual_j14.txt AC 24 ms 748 KB
manual_j15.txt AC 23 ms 928 KB
manual_j2.txt AC 28 ms 1692 KB
manual_j3.txt AC 22 ms 928 KB
manual_j4.txt AC 23 ms 844 KB
manual_j5.txt AC 23 ms 800 KB
manual_j6.txt AC 24 ms 932 KB
manual_j7.txt AC 22 ms 924 KB
manual_j8.txt AC 22 ms 928 KB
manual_j9.txt AC 22 ms 920 KB
manual_k1.txt AC 29 ms 1952 KB
manual_k2.txt AC 30 ms 2080 KB
random_01.txt AC 29 ms 1836 KB
random_02.txt AC 29 ms 1700 KB
random_03.txt AC 29 ms 1700 KB
random_04.txt AC 29 ms 1692 KB
random_05.txt AC 28 ms 1432 KB
random_06.txt AC 27 ms 1436 KB
random_max_01.txt AC 30 ms 1956 KB
random_max_02.txt AC 30 ms 1964 KB
random_max_03.txt AC 30 ms 2076 KB
random_max_04.txt AC 29 ms 1952 KB
random_max_05.txt AC 31 ms 1884 KB
random_max_06.txt AC 30 ms 1956 KB
random_max_07.txt AC 30 ms 1956 KB
random_max_08.txt AC 28 ms 1692 KB
random_max_09.txt AC 29 ms 1696 KB
random_max_10.txt AC 29 ms 1824 KB
sample_01.txt AC 24 ms 800 KB
sample_02.txt AC 22 ms 924 KB
sample_03.txt AC 22 ms 928 KB
sample_04.txt AC 24 ms 928 KB
white_01.txt AC 31 ms 2012 KB
white_02.txt AC 33 ms 2204 KB
white_03.txt AC 31 ms 2084 KB
white_04.txt AC 29 ms 1960 KB