Submission #342597


Source Code Expand

#include <type_traits>
#include <functional>
#include <limits>
#include <queue>
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
namespace lc {
template <class CapacityType>
struct EdgeWithCapacity {
	int to;
	CapacityType capacity;
	EdgeWithCapacity() : to(0), capacity() { }
	EdgeWithCapacity(int to, const CapacityType &capacity)
		: to(to), 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 HasWeight {
private:
	static std::false_type check(...);
public:
	static const bool value = decltype(check(EdgeType()))::value;
};
}
namespace lc {
template <class EdgeType>
struct ResidualEdge : public EdgeType {
	int rev;
	template <class... Args>
	ResidualEdge(int rev, Args&&... args)
		: EdgeType(args...)
		, rev(rev)
	{ }
};
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)
	-> typename std::enable_if<
		!HasWeight<EdgeType>::value, ResidualAdjacencyList<EdgeType>>::type
{
	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();
		}
	}
	return result;
}
}
namespace lc {
template <class EdgeType>
auto maxflow_dinic(
	int source, int sink, ResidualAdjacencyList<EdgeType> &graph)
	-> decltype(EdgeType().capacity)
{
	typedef decltype(EdgeType().capacity) capacity_type;
	const capacity_type inf = std::numeric_limits<capacity_type>::max();
	const int n = graph.size();
	capacity_type flow = 0;
	while(true){
		std::vector<int> level(n, -1);
		std::queue<int> q;
		level[source] = 0;
		q.push(source);
		while(!q.empty()){
			const int u = q.front();
			q.pop();
			for(const auto &e : graph[u]){
				const int v = e.to;
				if(e.capacity <= 0 || level[v] >= 0){ continue; }
				level[v] = level[u] + 1;
				q.push(v);
			}
		}
		if(level[sink] < 0){ break; }
		std::vector<size_t> iteration(n, 0);
		while(true){
			std::function<capacity_type(int, capacity_type)> dfs =
				[&](int u, capacity_type limit) -> capacity_type {
					if(u == sink){ return limit; }
					for(; iteration[u] < graph[u].size(); ++iteration[u]){
						auto &e = graph[u][iteration[u]];
						const int v = e.to;
						if(e.capacity <= 0 || level[u] >= level[v]){ continue; }
						const capacity_type diff =
							dfs(v, std::min(e.capacity, limit));
						if(diff > 0){
							e.capacity -= diff;
							graph[v][e.rev].capacity += diff;
							return diff;
						}
					}
					return 0;
				};
			const auto f = dfs(source, inf);
			if(f <= 0){ break; }
			flow += f;
		}
	}
	return flow;
}
}
namespace lc {
template <class EdgeType>
auto maxflow_reflow(
	int source, int sink, ResidualAdjacencyList<EdgeType> &graph)
	-> decltype(EdgeType().capacity)
{
	const int n = graph.size();
	std::vector<int> prev_v(n, -1), prev_e(n);
	std::queue<int> q;
	prev_v[source] = source;
	q.push(source);
	while(!q.empty()){
		const int u = q.front();
		q.pop();
		for(size_t i = 0; i < graph[u].size(); ++i){
			const auto &e = graph[u][i];
			const int v = e.to;
			if(e.capacity == 0 || prev_v[v] >= 0){ continue; }
			prev_v[v] = u;
			prev_e[v] = i;
			if(v == sink){ break; }
			q.push(v);
		}
	}
	if(prev_v[sink] < 0){ return 0; }
	int cur = sink;
	while(cur != source){
		const int u = prev_v[cur];
		const int i = prev_e[cur];
		auto &e = graph[u][i];
		--e.capacity;
		++graph[cur][e.rev].capacity;
		cur = u;
	}
	return 1;
}
}
using namespace std;
typedef lc::EdgeWithCapacity<int> Edge;
inline int read_character(const string &s, int i){
	if(static_cast<size_t>(i) >= s.size()){ return 0; }
	return s[i];
}
int main(){
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<string> s(n);
	for(int i = 0; i < n; ++i){ cin >> s[i]; }
	vector<int> lengths(n);
	for(int i = 0; i < n; ++i){ lengths[i] = s[i].size(); }
	sort(lengths.begin(), lengths.end());
	int lower = n - 1, upper = lengths[0];
	for(int i = 0; i < n; ++i){ upper = min(upper, i + lengths[i]); }
	if(lower >= upper){
		cout << "NO" << endl;
		return 0;
	}
	bool answer = false;
	for(int c = 'a'; !answer && c <= 'z'; ++c){
		const int source = n + n, sink = source + 1;
		lc::AdjacencyList<Edge> graph(n + n + 2);
		for(int i = 0; i < n; ++i){
			graph.add_edge(source, i, 1);
			graph.add_edge(i + n, sink, 1);
			for(int j = 0; j < n; ++j){
				if(read_character(s[i], j) == c){
					graph.add_edge(i, j + n, 1);
				}else{
					graph.add_edge(i, j + n, 0);
				}
			}
		}
		auto residual = lc::make_residual(graph);
		vector<vector<int>> edge_table(n, vector<int>(n, -1));
		for(int i = 0; i < n; ++i){
			for(size_t j = 0; j < residual[i].size(); ++j){
				const auto &e = residual[i][j];
				if(n <= e.to && e.to < n + n){ edge_table[i][e.to - n] = j; }
			}
		}
		int flow = lc::maxflow_dinic(source, sink, residual);
		if(flow == n){ answer = true; }
		for(int i = 0; !answer && i < upper - lower; ++i){
			const int col = i % n;
			for(int j = 0; j < n; ++j){
				const int v = j, e = edge_table[j][col];
				if(read_character(s[j], i) == c){
					if(residual[v][e].capacity > 0){
						--residual[v][e].capacity;
					}else{
						const auto &edge = residual[v][e];
						--residual[edge.to][edge.rev].capacity;
						--flow;
						lc::maxflow_reflow(v, source, residual);
						lc::maxflow_reflow(sink, edge.to, residual);
					}
				}
				if(read_character(s[j], i + n) == c){
					++residual[v][e].capacity;
				}
			}
			flow += lc::maxflow_reflow(source, sink, residual);
			if(flow == n){ answer = true; }
		}
	}
	cout << (answer ? "YES" : "NO") << endl;
	return 0;
}

Submission Info

Submission Time
Task B - コメント
User logicmachine
Language C++11 (GCC 4.8.1)
Score 0
Code Size 6757 Byte
Status WA
Exec Time 2035 ms
Memory 3000 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 0 / 30 0 / 60
Status
AC × 2
AC × 14
WA × 4
AC × 22
WA × 7
TLE × 15
Set Name Test Cases
Sample sample_01.txt, sample_02.txt
Subtask1 sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt
Subtask2 subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt
Case Name Status Exec Time Memory
sample_01.txt AC 26 ms 1052 KB
sample_02.txt AC 25 ms 1044 KB
subtask1_01.txt AC 26 ms 1048 KB
subtask1_02.txt AC 26 ms 1048 KB
subtask1_03.txt AC 33 ms 1172 KB
subtask1_04.txt AC 34 ms 1176 KB
subtask1_05.txt AC 30 ms 1084 KB
subtask1_06.txt AC 34 ms 1076 KB
subtask1_07.txt AC 30 ms 1176 KB
subtask1_08.txt AC 28 ms 872 KB
subtask1_09.txt WA 26 ms 1048 KB
subtask1_10.txt AC 25 ms 1040 KB
subtask1_11.txt AC 34 ms 1084 KB
subtask1_12.txt WA 24 ms 1044 KB
subtask1_13.txt AC 28 ms 1168 KB
subtask1_14.txt WA 37 ms 1044 KB
subtask1_15.txt WA 36 ms 1040 KB
subtask1_16.txt AC 34 ms 1084 KB
subtask2_01.txt TLE 2033 ms 1688 KB
subtask2_02.txt TLE 2032 ms 1680 KB
subtask2_03.txt AC 218 ms 1544 KB
subtask2_04.txt AC 797 ms 1568 KB
subtask2_05.txt AC 30 ms 1464 KB
subtask2_06.txt AC 27 ms 1308 KB
subtask2_07.txt WA 27 ms 1300 KB
subtask2_08.txt TLE 2031 ms 1652 KB
subtask2_09.txt TLE 2031 ms 1640 KB
subtask2_10.txt WA 349 ms 1508 KB
subtask2_11.txt TLE 2032 ms 1680 KB
subtask2_12.txt TLE 2035 ms 1676 KB
subtask2_13.txt AC 226 ms 1468 KB
subtask2_14.txt TLE 2033 ms 1596 KB
subtask2_15.txt TLE 2033 ms 1676 KB
subtask2_16.txt AC 1545 ms 1304 KB
subtask2_17.txt AC 799 ms 1076 KB
subtask2_18.txt AC 1687 ms 1116 KB
subtask2_19.txt AC 1226 ms 1200 KB
subtask2_20.txt TLE 2033 ms 1568 KB
subtask2_21.txt TLE 2033 ms 1624 KB
subtask2_22.txt TLE 2032 ms 1628 KB
subtask2_23.txt WA 1985 ms 1556 KB
subtask2_24.txt TLE 2032 ms 2960 KB
subtask2_25.txt TLE 2032 ms 1580 KB
subtask2_26.txt AC 603 ms 2912 KB
subtask2_27.txt TLE 2031 ms 2952 KB
subtask2_28.txt TLE 2033 ms 3000 KB