Submission #653648

#	Time	Username	Problem	Language	Result	Execution time	Memory
653648		ayalla	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	601 ms	262144 KiB

dango_maker

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//#define int long long int
#define endl '\n'
#define pb push_back
#define pi pair<int, int>
#define pii pair<int, pi>
#define fir first
#define sec second
#define MAXN 3005
#define mod 998244353
#define INF 1e9

struct hopcroft_karp
{
  vector<int> match;
  vector<int> dist;
  vector<vector<int>> adj;
  int n, m, t;

  hopcroft_karp(int a, int b)
  {
    n = a, m = b;
    t = n + m + 1;
    match.assign(t, n + m);
    dist.assign(t, 0);
    adj.assign(t, vector<int>{});
  }
  void add_edge(int u, int v)
  {
    adj[u].pb(v);
    adj[v].pb(u);
  }
  bool bfs()
  {
    queue<int> q;
    for (int u = 0; u < n; u++)
    {
      if (match[u] == n + m)
        dist[u] = 0, q.push(u);
      else
        dist[u] = INF;
    }
    dist[n + m] = INF;
    while (!q.empty())
    {
      int u = q.front();
      q.pop();
      if (dist[u] < dist[n + m])
      {
        for (auto const &v : adj[u])
        {
          if (dist[match[v]] == INF)
          {
            dist[match[v]] = dist[u] + 1;
            q.push(match[v]);
          }
        }
      }
    }
    return dist[n + m] < INF;
  }
  bool dfs(int u)
  {
    if (u < n + m)
    {
      for (auto const &v : adj[u])
      {
        if (dist[match[v]] == dist[u] + 1 && dfs(match[v]))
        {
          match[v] = u;
          match[u] = v;
          return true;
        }
      }
      dist[u] = INF;
      return false;
    }
    return true;
  }
  vector<pi> run()
  {
    int cnt = 0;
    while (bfs())
      for (int u = 0; u < n; u++)
        if (match[u] == n + m && dfs(u))
          cnt++;
    vector<pi> ans;
    for (int v = n; v < n + m; v++)
      if (match[v] < n + m)
        ans.pb({match[v], v});
    return ans;
  }
};
signed main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<string> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  vector<vector<int>> aux(n, vector<int>(m, -1));
  vector<vector<int>> aux2(n, vector<int>(m, -1));
  vector<pi> h, w;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j + 2 < m; j++)
    {
      if (v[i][j] == 'R' && v[i][j + 1] == 'G' && v[i][j + 2] == 'W')
      {
        h.pb({i, j});
        aux[i][j] = h.size() - 1;
        aux[i][j + 1] = h.size() - 1;
        aux[i][j + 2] = h.size() - 1;
      }
    }
  }
  for (int j = 0; j < m; j++)
  {
    for (int i = 0; i + 2 < n; i++)
    {
      if (v[i][j] == 'R' && v[i + 1][j] == 'G' && v[i + 2][j] == 'W')
      {
        w.pb({i, j});
        aux2[i][j] = w.size() - 1;
        aux2[i + 1][j] = w.size() - 1;
        aux2[i + 2][j] = w.size() - 1;
      }
    }
  }
  vector<pi> p;
  for (int i = 0; i < n; i++)
  {
    for (int j = 0; j < m; j++)
    {
      if (aux[i][j] != -1 && aux2[i][j] != -1)
        p.pb({aux[i][j], aux2[i][j]});
    }
  }
  sort(p.begin(), p.end());
  p.erase(unique(p.begin(), p.end()), p.end());
  hopcroft_karp hk(h.size(), w.size());
  for (auto const &i : p)
    hk.add_edge(i.fir, h.size() + i.sec);
  int ans = h.size() + w.size() - hk.run().size();
  cout << ans << endl;
  return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67