Submission #1794802

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

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

struct Bipartite_Matching
{
  vector< set< 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 u : graph[v]) {
      int 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);
  }
};


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;
    Bipartite_Matching flow(P + N);
    vector< int > ev[100000];
    for(int j = 0; j < N; j++) {
      for(int k : v[i][j]) {
        ev[k].emplace_back(j);
      }
    }
    int k = 0;
    int f = 0;
    for(int j = 0; j < P; j++) {
      while(k < P && k - j < N) {
        for(auto &addidx : ev[k]) {
          flow.graph[addidx + P].emplace(k);
          flow.graph[k].emplace(addidx + P);
          if(flow.match[k] == -1) {
            ++flow.timestamp;
            f += flow.dfs(k);
          }
          if(flow.match[addidx + P] == -1) {
            ++flow.timestamp;
            f += flow.dfs(addidx + P);
          }
        }
        ++k;
      }


      if(f == N) {
        cout << "YES" << endl;
        return (0);
      }

      for(auto &delidx : ev[j]) {
        bool update = false;
        if(flow.match[delidx + P] == j) {
          flow.match[delidx + P] = flow.match[j] = -1;
          flow.graph[delidx + P].erase(j);
          --f;
          update = true;
        }
        flow.graph[j].erase(delidx + P);
        flow.graph[delidx + P].erase(j);
        if(update) {
          ++flow.timestamp;
          f += flow.dfs(k);
          ++flow.timestamp;
          f += flow.dfs(delidx + P);
        }
      }
    }
  }

  cout << "NO" << endl;
}

Submission Info

Judge Result