結果
問題 | No.2238 Rock and Hole |
ユーザー | jiangly |
提出日時 | 2023-03-03 22:11:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 77 ms / 3,000 ms |
コード長 | 4,567 bytes |
コンパイル時間 | 2,828 ms |
コンパイル使用メモリ | 219,900 KB |
実行使用メモリ | 13,624 KB |
最終ジャッジ日時 | 2024-09-17 23:13:10 |
合計ジャッジ時間 | 3,967 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 1 ms
5,376 KB |
testcase_07 | AC | 1 ms
5,376 KB |
testcase_08 | AC | 2 ms
5,376 KB |
testcase_09 | AC | 2 ms
5,376 KB |
testcase_10 | AC | 5 ms
5,376 KB |
testcase_11 | AC | 14 ms
9,500 KB |
testcase_12 | AC | 13 ms
9,004 KB |
testcase_13 | AC | 12 ms
8,596 KB |
testcase_14 | AC | 7 ms
6,128 KB |
testcase_15 | AC | 5 ms
5,376 KB |
testcase_16 | AC | 25 ms
13,368 KB |
testcase_17 | AC | 29 ms
13,624 KB |
testcase_18 | AC | 15 ms
10,684 KB |
testcase_19 | AC | 77 ms
8,916 KB |
testcase_20 | AC | 23 ms
9,132 KB |
testcase_21 | AC | 24 ms
9,012 KB |
testcase_22 | AC | 15 ms
8,228 KB |
testcase_23 | AC | 2 ms
5,376 KB |
ソースコード
#include <bits/stdc++.h> using i64 = long long; template<class T> struct MaxFlow { struct _Edge { int to; T cap; _Edge(int to, T cap) : to(to), cap(cap) {} }; int n; std::vector<_Edge> e; std::vector<std::vector<int>> g; std::vector<int> cur, h; MaxFlow() {} MaxFlow(int n) { init(n); } void init(int n) { this->n = n; e.clear(); g.assign(n, {}); cur.resize(n); h.resize(n); } bool bfs(int s, int t) { h.assign(n, -1); std::queue<int> que; h[s] = 0; que.push(s); while (!que.empty()) { const int u = que.front(); que.pop(); for (int i : g[u]) { auto [v, c] = e[i]; if (c > 0 && h[v] == -1) { h[v] = h[u] + 1; if (v == t) { return true; } que.push(v); } } } return false; } T dfs(int u, int t, T f) { if (u == t) { return f; } auto r = f; for (int &i = cur[u]; i < int(g[u].size()); ++i) { const int j = g[u][i]; auto [v, c] = e[j]; if (c > 0 && h[v] == h[u] + 1) { auto a = dfs(v, t, std::min(r, c)); e[j].cap -= a; e[j ^ 1].cap += a; r -= a; if (r == 0) { return f; } } } return f - r; } void addEdge(int u, int v, T c) { g[u].push_back(e.size()); e.emplace_back(v, c); g[v].push_back(e.size()); e.emplace_back(u, 0); } T flow(int s, int t) { T ans = 0; while (bfs(s, t)) { cur.assign(n, 0); ans += dfs(s, t, std::numeric_limits<T>::max()); } return ans; } std::vector<bool> minCut() { std::vector<bool> c(n); for (int i = 0; i < n; i++) { c[i] = (h[i] != -1); } return c; } struct Edge { int from; int to; T cap; T flow; }; std::vector<Edge> edges() { std::vector<Edge> a; for (int i = 0; i < e.size(); i += 2) { Edge x; x.from = e[i + 1].to; x.to = e[i].to; x.cap = e[i].cap + e[i + 1].cap; x.flow = e[i + 1].cap; a.push_back(x); } return a; } }; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int H, W; std::cin >> H >> W; std::vector<std::string> s(H); int cnt = 0; MaxFlow<int> g(H * W + 2); int S = H * W, T = S + 1; for (int i = 0; i < H; i++) { std::cin >> s[i]; for (int j = 0; j < W; j++) { if (s[i][j] == 'r') { g.addEdge(S, i * W + j, 1); cnt++; } if (s[i][j] == 'h') { g.addEdge(i * W + j, T, 1); } } } for (int i = 0; i < H; i++) { int k = -1; for (int j = 0; j < W; j++) { if (s[i][j] == 'h') { k = j; } if (s[i][j] == 'r') { if (k != -1) { g.addEdge(i * W + j, i * W + k, 1); } } } k = -1; for (int j = W - 1; j >= 0; j--) { if (s[i][j] == 'h') { k = j; } if (s[i][j] == 'r') { if (k != -1) { g.addEdge(i * W + j, i * W + k, 1); } } } } for (int j = 0; j < W; j++) { int k = -1; for (int i = 0; i < H; i++) { if (s[i][j] == 'h') { k = i; } if (s[i][j] == 'r') { if (k != -1) { g.addEdge(i * W + j, k * W + j, 1); } } } k = -1; for (int i = H - 1; i >= 0; i--) { if (s[i][j] == 'h') { k = i; } if (s[i][j] == 'r') { if (k != -1) { g.addEdge(i * W + j, k * W + j, 1); } } } } if (g.flow(S, T) == cnt) { std::cout << "Yes\n"; } else { std::cout << "No\n"; } return 0; }