Submission #97979

#TimeUsernameProblemLanguageResultExecution timeMemory
97979AnaiDango Maker (JOI18_dango_maker)C++14
33 / 100
534 ms263168 KiB
#include <algorithm> #include <bitset> #include <cstdio> #include <iostream> #include <vector> using namespace std; const int N = 3005; vector<int> g[N * N]; vector<int> st, dr; bitset<N * N> f; vector<int> used; vector<string> mx; int n, m, fp; static int cod(int l, int c) { return 1 + l * m + c; } static bool match(int u) { if (f[u]) return false; f[u] = 1; for (auto v: g[u]) if (!dr[v]) { st[u] = v; dr[v] = u; return true; } for (auto v: g[u]) if (match(dr[v])) { st[u] = v; dr[v] = u; return true; } return false;} int main() { #ifdef HOME freopen("joi_dango.in", "r", stdin); freopen("joi_dango.out", "w", stdout); #endif ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int add, ant; cin >> n >> m; mx.resize(n); for (auto &line: mx) cin >> line; ant = 0; for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) if (mx[i][j] == 'R') { bool hor = j + 2 < m ? (mx[i][j + 1] == 'G' && mx[i][j + 2] == 'W') : 0; bool ver = i + 2 < n ? (mx[i + 1][j] == 'G' && mx[i + 2][j] == 'W') : 0; ant+= int(hor) + int(ver); if (hor || ver) used.push_back(cod(i, j)); if (hor && ver) { g[used.size()].push_back(used.size()); } } for (int i = 2; i < n; ++i) for (int j = 2; j < m; ++j) if (mx[i][j] == 'W') { bool hor = mx[i][j - 2] == 'R' && mx[i][j - 1] == 'G'; bool ver = mx[i - 2][j] == 'R' && mx[i - 1][j] == 'G'; if (hor && ver) { int h = lower_bound(begin(used), end(used), cod(i - 2, j)) - begin(used) + 1; int v = lower_bound(begin(used), end(used), cod(i, j - 2)) - begin(used) + 1; g[v].push_back(h); } } for (int i = 1; i < n - 1; ++i) for (int j = 1; j < m - 1; ++j) if (mx[i][j] == 'G') { if (mx[i - 1][j] == 'R' && mx[i + 1][j] == 'W') if (mx[i][j - 1] == 'R' && mx[i][j + 1] == 'W') { int h = lower_bound(begin(used), end(used), cod(i - 1, j)) - begin(used) + 1; int v = lower_bound(begin(used), end(used), cod(i, j - 1)) - begin(used) + 1; g[v].push_back(h); } } mx.clear(); mx.shrink_to_fit(); st.resize(used.size() + 5); dr.resize(used.size() + 5); do { f = 0; add = 0; for (int i = 1; i <= used.size(); ++i) if (!st[i] && !f[i]) add+= int(match(i)); ant-= add; } while (add); cout << ant << endl; return 0; }

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:90:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i <= used.size(); ++i)
                   ~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...