Submission #342434
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;
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;
}
template <class EdgeType>
auto maxflow_decrease(
int v, int e, int source, int sink,
ResidualAdjacencyList<EdgeType> &graph)
-> decltype(EdgeType().capacity)
{
typedef decltype(EdgeType().capacity) capacity_type;
if(graph[v][e].capacity > 0){
--graph[v][e].capacity;
return 0;
}
--graph[graph[v][e].to][graph[v][e].rev].capacity;
maxflow_reflow(v, source, graph);
maxflow_reflow(sink, graph[v][e].to, graph);
return 1 - maxflow_reflow(source, sink, graph);
}
}
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));
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){
if(read_character(s[j], i) == c){
flow -= lc::maxflow_decrease(
j, edge_table[j][col], source, sink, residual);
}
if(read_character(s[j], i + n) == c){
++residual[j][edge_table[j][col]].capacity;
}
}
flow += 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 |
6974 Byte |
Status |
WA |
Exec Time |
2038 ms |
Memory |
3068 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
0 / 30 |
0 / 60 |
Status |
|
|
|
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 |
30 ms |
1004 KB |
sample_02.txt |
AC |
29 ms |
1004 KB |
subtask1_01.txt |
AC |
27 ms |
1044 KB |
subtask1_02.txt |
AC |
28 ms |
996 KB |
subtask1_03.txt |
AC |
37 ms |
1172 KB |
subtask1_04.txt |
AC |
37 ms |
1128 KB |
subtask1_05.txt |
AC |
31 ms |
1128 KB |
subtask1_06.txt |
AC |
36 ms |
1192 KB |
subtask1_07.txt |
AC |
29 ms |
1128 KB |
subtask1_08.txt |
AC |
28 ms |
1004 KB |
subtask1_09.txt |
WA |
28 ms |
1052 KB |
subtask1_10.txt |
AC |
28 ms |
1048 KB |
subtask1_11.txt |
AC |
37 ms |
1128 KB |
subtask1_12.txt |
WA |
28 ms |
1048 KB |
subtask1_13.txt |
AC |
32 ms |
1132 KB |
subtask1_14.txt |
AC |
41 ms |
1120 KB |
subtask1_15.txt |
AC |
34 ms |
1052 KB |
subtask1_16.txt |
AC |
38 ms |
1136 KB |
subtask2_01.txt |
AC |
205 ms |
1516 KB |
subtask2_02.txt |
TLE |
2035 ms |
1668 KB |
subtask2_03.txt |
AC |
217 ms |
1700 KB |
subtask2_04.txt |
TLE |
2033 ms |
1620 KB |
subtask2_05.txt |
AC |
31 ms |
1704 KB |
subtask2_06.txt |
AC |
30 ms |
1248 KB |
subtask2_07.txt |
WA |
30 ms |
1260 KB |
subtask2_08.txt |
AC |
201 ms |
1692 KB |
subtask2_09.txt |
TLE |
2033 ms |
1672 KB |
subtask2_10.txt |
TLE |
2034 ms |
1632 KB |
subtask2_11.txt |
TLE |
2036 ms |
1660 KB |
subtask2_12.txt |
AC |
1886 ms |
1664 KB |
subtask2_13.txt |
AC |
445 ms |
1648 KB |
subtask2_14.txt |
TLE |
2033 ms |
1664 KB |
subtask2_15.txt |
AC |
973 ms |
1636 KB |
subtask2_16.txt |
TLE |
2033 ms |
1384 KB |
subtask2_17.txt |
AC |
1406 ms |
1252 KB |
subtask2_18.txt |
TLE |
2033 ms |
1388 KB |
subtask2_19.txt |
TLE |
2034 ms |
1292 KB |
subtask2_20.txt |
TLE |
2035 ms |
1620 KB |
subtask2_21.txt |
TLE |
2035 ms |
1640 KB |
subtask2_22.txt |
TLE |
2033 ms |
1672 KB |
subtask2_23.txt |
TLE |
2038 ms |
1644 KB |
subtask2_24.txt |
TLE |
2034 ms |
2980 KB |
subtask2_25.txt |
TLE |
2036 ms |
1688 KB |
subtask2_26.txt |
AC |
1457 ms |
3044 KB |
subtask2_27.txt |
TLE |
2033 ms |
3060 KB |
subtask2_28.txt |
TLE |
2033 ms |
3068 KB |