結果

問題 No.2238 Rock and Hole
コンテスト
ユーザー emthrm
提出日時 2023-03-03 22:25:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 66 ms / 3,000 ms
コード長 4,005 bytes
コンパイル時間 3,057 ms
コンパイル使用メモリ 269,320 KB
実行使用メモリ 14,240 KB
最終ジャッジ日時 2024-09-17 23:28:32
合計ジャッジ時間 4,075 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,m,n) for(int i=(m);i<(n);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
using ll = long long;
constexpr int INF = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr double EPS = 1e-8;
constexpr int MOD = 998244353;
// constexpr int MOD = 1000000007;
constexpr int DY4[]{1, 0, -1, 0}, DX4[]{0, -1, 0, 1};
constexpr int DY8[]{1, 1, 0, -1, -1, -1, 0, 1};
constexpr int DX8[]{0, -1, -1, -1, 0, 1, 1, 1};
template <typename T, typename U>
inline bool chmax(T& a, U b) { return a < b ? (a = b, true) : false; }
template <typename T, typename U>
inline bool chmin(T& a, U b) { return a > b ? (a = b, true) : false; }
struct IOSetup {
  IOSetup() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << fixed << setprecision(20);
  }
} iosetup;

template <typename T>
struct Dinic {
  struct Edge {
    int dst, rev;
    T cap;
    explicit Edge(const int dst, const T cap, const int rev)
        : dst(dst), rev(rev), cap(cap) {}
  };

  std::vector<std::vector<Edge>> graph;

  explicit Dinic(const int n) : graph(n), level(n), itr(n) {}

  void add_edge(const int src, const int dst, const T cap) {
    graph[src].emplace_back(dst, cap, graph[dst].size());
    graph[dst].emplace_back(src, 0, graph[src].size() - 1);
  }

  T maximum_flow(const int s, const int t,
                 T limit = std::numeric_limits<T>::max()) {
    T res = 0;
    while (limit > 0) {
      std::fill(level.begin(), level.end(), -1);
      level[s] = 0;
      std::queue<int> que;
      que.emplace(s);
      while (!que.empty()) {
        const int ver = que.front();
        que.pop();
        for (const Edge& e : graph[ver]) {
          if (level[e.dst] == -1 && e.cap > 0) {
            level[e.dst] = level[ver] + 1;
            que.emplace(e.dst);
          }
        }
      }
      if (level[t] == -1) break;
      std::fill(itr.begin(), itr.end(), 0);
      while (limit > 0) {
        const T f = dfs(s, t, limit);
        if (f == 0) break;
        limit -= f;
        res += f;
      }
    }
    return res;
  }

 private:
  std::vector<int> level, itr;

  T dfs(const int ver, const int t, const T flow) {
    if (ver == t) return flow;
    for (; std::cmp_less(itr[ver], graph[ver].size()); ++itr[ver]) {
      Edge& e = graph[ver][itr[ver]];
      if (level[ver] < level[e.dst] && e.cap > 0) {
        const T tmp = dfs(e.dst, t, std::min(flow, e.cap));
        if (tmp > 0) {
          e.cap -= tmp;
          graph[e.dst][e.rev].cap += tmp;
          return tmp;
        }
      }
    }
    return 0;
  }
};

int main() {
  int h, w; cin >> h >> w;
  vector<string> s(h); REP(i, h) cin >> s[i];
  vector ids(h, vector(w, -1));
  int n = 0;
  REP(i, h) REP(j, w) {
    if (s[i][j] != '.') ids[i][j] = n++;
  }
  int r = 0;
  Dinic<int> dinic(n + 2);
  const int src = n, dst = src + 1;
  REP(i, h) {
    vector<int> row;
    REP(j, w) {
      if (s[i][j] == 'h') {
        dinic.add_edge(ids[i][j], dst, 1);
        row.emplace_back(j);
      }
    }
    ranges::reverse(row);
    int left = -1;
    REP(j, w) {
      if (!row.empty() && row.back() == j) {
        row.pop_back();
        left = j;
      }
      if (s[i][j] == 'r') {
        ++r;
        dinic.add_edge(src, ids[i][j], 1);
        if (left != -1) dinic.add_edge(ids[i][j], ids[i][left], 1);
        if (!row.empty()) dinic.add_edge(ids[i][j], ids[i][row.back()], 1);
      }
    }
  }
  REP(j, w) {
    vector<int> col;
    REP(i, h) {
      if (s[i][j] == 'h') col.emplace_back(i);
    }
    ranges::reverse(col);
    int up = -1;
    REP(i, h) {
      if (!col.empty() && col.back() == i) {
        col.pop_back();
        up = i;
      }
      if (s[i][j] == 'r') {
        if (up != -1) dinic.add_edge(ids[i][j], ids[up][j], 1);
        if (!col.empty()) dinic.add_edge(ids[i][j], ids[col.back()][j], 1);
      }
    }
  }
  cout << (dinic.maximum_flow(src, dst, r) == r ? "Yes\n" : "No\n");
  return 0;
}
0