#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++)
{
if (h[i] == w[j])
hk.add_edge(i, h.size() + j);
}
}
int ans = h.size() + w.size() - hk.run().size();
cout << ans << endl;
return 0;
}
Compilation message
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++)
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
212 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
