// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx")
// #pragma comment(linker, "/stack:200000000"]
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <bitset>
#include <stack>
#include <random>
#include <fstream>
#include <sstream>
#include <chrono>
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define hm unordered_map
#define pii pair<int, int>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define cinv(v) for (auto& x: v) cin >> x
#define fr(i, n) for (int i = 0; i < n; ++i)
#define fl(i, l, n) for (int i = l; i < n; ++i)
// #define int ll
template <typename T1, typename T2> inline bool chkmin(T1 &x, const T2 &y) {if (x > y) {x = y; return 1;} return 0;}
template <typename T1, typename T2> inline bool chkmax(T1 &x, const T2 &y) {if (x < y) {x = y; return 1;} return 0;}
using namespace std;
#ifdef LOCAL
#define dbg(x) cerr << #x << " : " << x << '\n'
const int maxn = 20;
#else
#define dbg(x)
const int maxn = 2e5 + 20;
#endif
//tg: @galebickosikasa
ostream& operator << (ostream& out, const pii& v) {
out << v.fi << ", " << v.se;
return out;
}
template<typename T> ostream& operator << (ostream& out, const vector<T>& v) {
for (auto& x: v) out << x << " ";
return out;
}
istream& operator >> (istream& in, pii& a) {
in >> a.fi >> a.se;
return in;
}
const ll inf = (ll) 2e9;
const ld pi = asin (1) * 2;
const ld eps = 1e-8;
const ll mod = (ll)1e9 + 7;
const ll ns = 97;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
char goo[3000][3000];
int a[3000][3000], it[1000 * 3000 + 5];
short d[1000 * 3000 + 5];
struct edge {
int to, f, c;
};
vector<int> g[1000 * 3000 + 10];
edge edges[1000 * 3000 + 10];
int ind = 0;
inline int bfs (int st, int fin) {
for (int i = 0; i <= fin; ++i) d[i] = 100;
d[st] = 0;
queue<int> a;
a.push (st);
while (!a.empty ()) {
int v = a.front ();
a.pop ();
for (auto& u: g[v]) {
if (d[edges[u].to] == inf && edges[u].c - edges[u].f > 0) {
d[edges[u].to] = d[v] + 1;
a.push (edges[u].to);
}
}
}
return d[fin] < 100;
}
int dfs (int v, int t, int c = inf) {
if (v == t) return c;
while (it[v] < sz (g[v])) {
auto& e = edges[g[v][it[v]]];
if (d[e.to] == d[v] + 1 && e.c - e.f > 0) {
int delta = dfs (e.to, t, min (c, e.c - e.f));
if (delta > 0) {
auto& _e = edges[g[v][it[v]] ^ 1];
e.f += delta;
_e.f -= delta;
return delta;
}
}
++it[v];
}
return 0;
}
signed main () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) cin >> goo[i][j];
for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) a[i][j] = -1;
int c = 0;
for (int i = 0; i < n; ++i) {
for (int j = 2; j < m; ++j) {
if (goo[i][j - 2] == 'R' && goo[i][j - 1] == 'G' && goo[i][j] == 'W') {
a[i][j - 2] = a[i][j - 1] = a[i][j] = c++;
}
}
}
int last = c;
for (int i = 2; i < n; ++i) {
for (int j = 0; j < m; ++j) {
if (goo[i - 2][j] == 'R' && goo[i - 1][j] == 'G' && goo[i][j] == 'W') {
for (int k = i - 2; k <= i; ++k) {
if (a[k][j] != -1) {
int u = c, v = a[k][j];
dbg (v);
dbg (u);
g[v].pb (ind);
edges[ind++] = {u, 0, 1};
g[u].pb (ind);
edges[ind++] = {v, 0, 0};
}
}
++c;
}
}
}
int st = c, fin = st + 1;
dbg ("first");
for (int i = 0; i < last; ++i) {
dbg (i);
g[st].pb (ind);
edges[ind++] = {i, 0, 1};
g[i].pb (ind);
edges[ind++] = {st, 0, 0};
}
dbg ("second");
for (int i = last; i < c; ++i) {
dbg (i);
g[i].pb (ind);
edges[ind++] = {fin, 0, 1};
g[fin].pb (ind);
edges[ind++] = {i, 0, 0};
}
while (bfs (st, fin)) {
while (dfs (st, fin));
for (int i = 0; i <= fin; ++i) it[i] = 0;
}
int res = 0;
for (auto& x: g[st]) {
res += edges[x].f;
}
dbg (res);
cout << c - res << '\n';
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 2 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 3 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 4 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 5 |
Correct |
48 ms |
70892 KB |
Output is correct |
| 6 |
Incorrect |
48 ms |
70892 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 2 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 3 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 4 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 5 |
Correct |
48 ms |
70892 KB |
Output is correct |
| 6 |
Incorrect |
48 ms |
70892 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 2 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 3 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 4 |
Correct |
48 ms |
70764 KB |
Output is correct |
| 5 |
Correct |
48 ms |
70892 KB |
Output is correct |
| 6 |
Incorrect |
48 ms |
70892 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
