제출 #653634

#제출 시각아이디문제언어결과실행 시간메모리
653634ayallaDango Maker (JOI18_dango_maker)C++14
0 / 100
1 ms212 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; //#define int long long int #define endl '\n' #define pb push_back #define pi pair<int, int> #define pii pair<int, pi> #define fir first #define sec second #define MAXN 3005 #define mod 998244353 #define INF 1e9 struct hopcroft_karp { vector<int> match; vector<int> dist; vector<vector<int>> adj; int n, m, t; hopcroft_karp(int a, int b) { n = a, m = b; t = n + m + 1; match.assign(t, n + m); dist.assign(t, 0); adj.assign(t, vector<int>{}); } void add_edge(int u, int v) { adj[u].pb(v); adj[v].pb(u); } bool bfs() { queue<int> q; for (int u = 0; u < n; u++) { if (match[u] == n + m) dist[u] = 0, q.push(u); else dist[u] = INF; } dist[n + m] = INF; while (!q.empty()) { int u = q.front(); q.pop(); if (dist[u] < dist[n + m]) { for (auto const &v : adj[u]) { if (dist[match[v]] == INF) { dist[match[v]] = dist[u] + 1; q.push(match[v]); } } } } return dist[n + m] < INF; } bool dfs(int u) { if (u < n + m) { for (auto const &v : adj[u]) { if (dist[match[v]] == dist[u] + 1 && dfs(match[v])) { match[v] = u; match[u] = v; return true; } } dist[u] = INF; return false; } return true; } vector<pi> run() { int cnt = 0; while (bfs()) for (int u = 0; u < n; u++) if (match[u] == n + m && dfs(u)) cnt++; vector<pi> ans; for (int v = n; v < n + m; v++) if (match[v] < n + m) ans.pb({match[v], v}); return ans; } }; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int n, m; cin >> n >> m; vector<string> v(n); for (int i = 0; i < n; i++) cin >> v[i]; vector<pi> h, w; for (int i = 0; i < n; i++) { for (int j = 0; j + 2 < m; j++) { if (v[i][j] == 'R' && v[i][j + 1] == 'G' && v[i][j + 2] == 'W') h.pb({i, j}); } } for (int j = 0; j < m; j++) { for (int i = 0; i + 2 < n; i++) { if (v[i][j] == 'R' && v[i + 1][j] == 'G' && v[i + 2][j] == 'W') w.pb({i, j}); } } hopcroft_karp hk(h.size(), w.size()); for (int i = 0; i < h.size(); i++) { for (int j = 0; j < w.size(); j++) { if (h[i] == w[j]) hk.add_edge(i, h.size() + j); } } int ans = h.size() + w.size() - hk.run().size(); cout << ans << endl; return 0; }

컴파일 시 표준 에러 (stderr) 메시지

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:129:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |   for (int i = 0; i < h.size(); i++)
      |                   ~~^~~~~~~~~~
dango_maker.cpp:131:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  131 |     for (int j = 0; j < w.size(); j++)
      |                     ~~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...