Submission #336524

#TimeUsernameProblemLanguageResultExecution timeMemory
336524GalebickosikasaDango Maker (JOI18_dango_maker)C++17
33 / 100
386 ms262148 KiB
// #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]; int d[3000 * 3000 + 5], it[3000 * 3000 + 5]; struct edge { int to, f, c; }; vector<int> g[3000 * 3000 + 10]; vector<edge> edges; inline int bfs (int st, int fin) { for (int i = 0; i <= fin; ++i) d[i] = inf; 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] < inf; } 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 (sz (edges)); edges.pb ({u, 0, 1}); g[u].pb (sz (edges)); edges.pb ({v, 0, 0}); } } ++c; } } } int st = c, fin = st + 1; dbg ("first"); for (int i = 0; i < last; ++i) { dbg (i); g[st].pb (sz (edges)); edges.pb ({i, 0, 1}); g[i].pb (sz (edges)); edges.pb ({st, 0, 0}); } dbg ("second"); for (int i = last; i < c; ++i) { dbg (i); g[i].pb (sz (edges)); edges.pb ({fin, 0, 1}); g[fin].pb (sz (edges)); edges.pb ({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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...