Submission #1794822

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

using vi = vector< int >;
using vii = vector< vi >;

struct Bipartite_Matching
{
  vector< vector< int > > graph;
  vector< int > match, alive, used;
  int timestamp;

  Bipartite_Matching(int n)
  {
    timestamp = 0;
    graph.resize(n);
    alive.assign(n, 1);
    used.assign(n, 0);
    match.assign(n, -1);
  }

  void add_edge(int u, int v)
  {
    graph[u].push_back(v);
    graph[v].push_back(u);
  }

  bool dfs(int v)
  {
    used[v] = timestamp;
    for(int i = 0; i < graph[v].size(); i++) {
      int u = graph[v][i], w = match[u];
      if(alive[u] == 0) continue;
      if(w == -1 || (used[w] != timestamp && dfs(w))) {
        match[v] = u;
        match[u] = v;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching()
  {
    int ret = 0;
    for(int i = 0; i < graph.size(); i++) {
      if(alive[i] == 0) continue;
      if(match[i] == -1) {
        ++timestamp;
        ret += dfs(i);
      }
    }
    return (ret);
  }
};

struct Fix_Matching : Bipartite_Matching
{
  Fix_Matching(int sz) : Bipartite_Matching(sz) {}

  int add(int k) // 加える
  {
    alive[k] = 1;
    ++timestamp;
    return (dfs(k));
  }

  int kill(int k) // 消す
  {
    alive[k] = 0;
    if(match[k] == -1) return (0);
    match[match[k]] = -1;
    ++timestamp;
    int ret = dfs(match[k]);
    match[k] = -1;
    return (ret - 1);
  }
};

int main()
{
  int N;
  cin >> N;
  vector< vii > v(26, vii(N));
  for(int i = 0; i < N; i++) {
    string s;
    cin >> s;
    for(int j = 0; j < s.size(); j++) {
      v[s[j] - 'a'][i].push_back(j);
    }
  }

  for(int i = 0; i < 26; i++) {
    const int P = 100000;
    Fix_Matching flow(P + N);
    for(int j = 0; j < N; j++) {
      for(int k : v[i][j]) {
        flow.add_edge(k, P + j);
      }
    }
    for(int j = 0; j < P; j++) flow.kill(j);
    int f = 0, k = 0;

    for(int j = 0; j < P; j++) {
      while(k < P && k - j < N) {
        f += flow.add(k++);
      }
      if(f == N) {
        cout << "YES" << endl;
        return (0);
      }
      f += flow.kill(j);
    }
  }
  cout << "NO" << endl;
}

Submission Info

Judge Result