Submission #653642

#	Time	Username	Problem	Language	Result	Execution time	Memory
653642		ayalla	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	2074 ms	4688 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<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});
    }
  }
  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});
    }
  }
  hopcroft_karp hk(h.size(), w.size());
  for (int i = 0; i < h.size(); i++)
  {
    for (int j = 0; j < w.size(); j++)
    {
      bool ok = 0;
      for (int x = w[j].fir; x <= w[j].fir + 2; x++)
      {
        for (int y = h[i].sec; y <= h[i].sec + 2; y++)
        {
          if (h[i].fir == x && w[j].sec == y)
            ok = 1;
        }
      }
      if (ok)
        hk.add_edge(i, h.size() + j);
    }
  }
  int ans = h.size() + w.size() - hk.run().size();
  cout << ans << endl;
  return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:129:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for (int i = 0; i < h.size(); i++)
      |                   ~~^~~~~~~~~~
dango_maker.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int j = 0; j < w.size(); j++)
      |                     ~~^~~~~~~~~~

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