Submission #1192876

#TimeUsernameProblemLanguageResultExecution timeMemory
1192876LucaLucaMDango Maker (JOI18_dango_maker)C++20
0 / 100
106 ms211856 KiB
#include <iostream> #include <vector> #include <algorithm> #include <cassert> using ll = long long; #define debug(x) #x << " = " << x << '\n' const int NMAX = 3000; char a[NMAX][NMAX]; int vertical[NMAX][NMAX], horizontal[NMAX][NMAX]; std::vector<int> g[NMAX * NMAX]; bool vis[NMAX * NMAX]; int l[NMAX], r[NMAX]; bool cupleaza(int u) { vis[u] = true; for (const auto &v : g[u]) { if (r[v] == -1) { r[v] = u; l[u] = v; return true; } } for (const auto &v : g[u]) { if (!vis[r[v]] && cupleaza(r[v])) { l[u] = v; r[v] = u; return true; } } return false; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); #endif std::ios_base::sync_with_stdio(false); std::cin.tie(0); int n, m; std::cin >> n >> m; for (int i = 0; i < n; i++) { std::string s; std::cin >> s; for (int j = 0; j < m; j++) { a[i][j] = s[j]; } } std::vector<int> vertl, vertr; std::vector<std::pair<int, int>> edges; int answer = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { vertical[i][j] = horizontal[i][j] = -1; } } for (int i = 0; i < n; i++) { for (int j = 0; j + 2 < m; j++) { if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') { vertl.push_back(i * m + j); vertical[i][j] = vertical[i][j + 1] = vertical[i][j + 2] = i * m + j; } } } for (int i = 0; i + 2 < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') { vertr.push_back(i * m + j); horizontal[i][j] = horizontal[i + 1][j] = horizontal[i + 2][j] = i * m + j; } } } for (int i = 0; i + 2 < n; i++) { for (int j = 0; j + 2 < m; j++) { if (vertical[i][j] != -1 && horizontal[i][j] != -1) { edges.push_back({vertical[i][j], horizontal[i][j]}); } } } std::sort(vertl.begin(), vertl.end()); vertl.erase(std::unique(vertl.begin(), vertl.end()), vertl.end()); std::sort(vertr.begin(), vertr.end()); vertr.erase(std::unique(vertr.begin(), vertr.end()), vertr.end()); for (auto &[x, y] : edges) { x = std::lower_bound(vertl.begin(), vertl.end(), x) - vertl.begin(); y = std::lower_bound(vertr.begin(), vertr.end(), y) - vertr.begin(); g[x].push_back(y); } std::vector<bool> atinge((int) vertr.size(), false); for (int i = 0; i < (int) vertl.size(); i++) { if (g[vertl[i]].empty()) { answer++; } else { for (const auto &j : g[vertl[i]]) { atinge[j] = true; } } } for (int i = 0; i < (int) vertr.size(); i++) { if (!atinge[i]) { answer++; } } bool repeat = true; for (int i = 0; i < (int) vertl.size(); i++) { l[i] = -1; } for (int i = 0; i < (int) vertr.size(); i++) { r[i] = -1; } while (repeat) { repeat = false; for (int i = 0; i < (int) vertl.size(); i++) { vis[i] = false; } for (int i = 0; i < (int) vertl.size(); i++) { if (l[i] == -1 && cupleaza(i)) { answer++; repeat = true; } } } std::cout << answer; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...