제출 #522024

#제출 시각아이디문제언어결과실행 시간메모리
522024MonarchuwuDango Maker (JOI18_dango_maker)C++17
0 / 100
108 ms212152 KiB
#include<iostream> #include<algorithm> #include<vector> #include<queue> using namespace std; typedef long long ll; const int N = 3000 + 3, N2 = N * N, inf = 1e9 + 7; int m, n; char c[N][N]; vector<int> vertexX; int cnt, num[2][2][N]; vector<int> g[N2]; void init_graph() { for (int i = 1, tmp; i <= m; ++i) { for (int j = 1; j <= n; ++j) if (c[i][j] == 'G') { // check ngang if (c[i][j - 1] == 'R' && c[i][j + 1] == 'W') { num[0][1][j] = ++cnt; vertexX.push_back(cnt); tmp = num[1][0][j + 1]; if (tmp) g[cnt].push_back(tmp); } // check dọc if (c[i - 1][j] == 'R' && c[i + 1][j] == 'W') { num[1][1][j] = ++cnt; tmp = num[0][0][j + 1]; if (tmp) g[tmp].push_back(cnt); } if (num[0][1][j] && num[1][1][j]) g[cnt - 1].push_back(cnt); } copy(num[0][1] + 1, num[0][1] + n + 1, num[0][0] + 1); fill(num[0][1] + 1, num[0][1] + n + 1, 0); copy(num[1][1] + 1, num[1][1] + n + 1, num[1][0] + 1); fill(num[1][1] + 1, num[1][1] + n + 1, 0); } } int mat[N2]; int dist[N2]; bool bfs() { queue<int> q; dist[0] = inf; for (int i : vertexX) if (mat[i]) dist[i] = inf; else { dist[i] = 0; q.push(i); } while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[mat[v]] == inf) { dist[mat[v]] = dist[u] + 1; q.push(mat[v]); } } } return dist[0] != inf; } bool dfs(int u) { for (int v : g[u]) { if (!mat[v] || (dist[mat[v]] == dist[u] + 1 && dfs(mat[v]))) { mat[v] = u, mat[u] = v; dist[u] = inf; return true; } } dist[u] = inf; return false; } int hopcroft_karp() { int ans(0); while (bfs()) { for (int i : vertexX) if (!mat[i] && dfs(i)) ++ans; } return ans; } int main() { cin.tie(NULL)->sync_with_stdio(false); cin >> m >> n; for (int i = 0; i < m; ++i) cin >> (c[i] + 1); init_graph(); cout << cnt - hopcroft_karp() << '\n'; } /** /\_/\ * (= ._.) * / >0 \>1 **/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...