結果

問題 No.2238 Rock and Hole
ユーザー otamay6otamay6
提出日時 2023-03-03 23:32:18
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 63 ms / 3,000 ms
コード長 3,093 bytes
コンパイル時間 2,515 ms
コンパイル使用メモリ 225,980 KB
実行使用メモリ 15,104 KB
最終ジャッジ日時 2024-09-18 00:33:03
合計ジャッジ時間 4,063 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 1 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 5 ms
6,940 KB
testcase_11 AC 37 ms
11,224 KB
testcase_12 AC 43 ms
11,620 KB
testcase_13 AC 33 ms
11,080 KB
testcase_14 AC 17 ms
7,552 KB
testcase_15 AC 7 ms
6,940 KB
testcase_16 AC 63 ms
14,720 KB
testcase_17 AC 57 ms
14,848 KB
testcase_18 AC 57 ms
15,104 KB
testcase_19 AC 30 ms
7,296 KB
testcase_20 AC 33 ms
9,024 KB
testcase_21 AC 26 ms
7,808 KB
testcase_22 AC 25 ms
8,576 KB
testcase_23 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define REP(i,n) for(int i=0,i##_len=int(n);i<i##_len;++i)
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
#define All(x) (x).begin(),(x).end()
#define rAll(x) (x).rbegin(),(x).rend()
using namespace std;
using ll = long long;

struct HopcroftKarp {
  vector< vector< int > > graph;
  vector< int > dist, match;
  vector< bool > used, vv;

  HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {}

  void add_edge(int u, int v) {
    graph[u].push_back(v);
  }

  void bfs() {
    dist.assign(graph.size(), -1);
    queue< int > que;
    for(int i = 0; i < graph.size(); i++) {
      if(!used[i]) {
        que.emplace(i);
        dist[i] = 0;
      }
    }

    while(!que.empty()) {
      int a = que.front();
      que.pop();
      for(auto &b : graph[a]) {
        int c = match[b];
        if(c >= 0 && dist[c] == -1) {
          dist[c] = dist[a] + 1;
          que.emplace(c);
        }
      }
    }
  }

  bool dfs(int a) {
    vv[a] = true;
    for(auto &b : graph[a]) {
      int c = match[b];
      if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) {
        match[b] = a;
        used[a] = true;
        return (true);
      }
    }
    return (false);
  }

  int bipartite_matching() {
    int ret = 0;
    while(true) {
      bfs();
      vv.assign(graph.size(), false);
      int flow = 0;
      for(int i = 0; i < graph.size(); i++) {
        if(!used[i] && dfs(i)) ++flow;
      }
      if(flow == 0) return (ret);
      ret += flow;
    }
  }

  void output() {
    for(int i = 0; i < match.size(); i++) {
      if(~match[i]) {
        cout << match[i] << "-" << i << endl;
      }
    }
  }
};
int main() {
    int h,w;
    cin>>h>>w;
    assert(h*w <= 100000);
    vector<string> s(h);
    REP(i,h) cin>>s[i];
    // 岩と穴に番号を付ける

    int X = 0, Y = 0;
    map<pair<int,int>, int> x, yw, yh;
    REP(i, h) REP(j, w) {
        if(s[i][j] == 'r'){
            x[pair<int,int>(i,j)] = X;
            X += 1;
        }
        if(s[i][j] == 'h') {
            yw[pair<int,int>(j, i)] = Y;
            yh[pair<int,int>(i, j)] = Y;
            Y += 1;
        }
    }
    HopcroftKarp G(X , Y);
    for (auto kvp: x) {  // X(1~X) から Y(X+1~X+Y) への辺
        pair<int,int> pos = kvp.first;
        int node = kvp.second;
        auto iter = yw.lower_bound(pair<int,int>(pos.second, pos.first));
        if(iter != yw.end() && iter->first.first == pos.second) {
            G.add_edge(node, iter->second);
        }
        if(iter != yw.begin()) {
            iter = prev(iter);
            if(iter->first.first == pos.second) {
                G.add_edge(node, iter->second);
            }
        }
        iter = yh.lower_bound(pos);
        if(iter != yh.end() && iter->first.first == pos.first) {
            G.add_edge(node, iter->second);
        }
        if(iter != yh.begin()) {
            iter = prev(iter);
            if(iter->first.first == pos.first) {
                G.add_edge(node, iter->second);
            }
        }
    }
    cout << (G.bipartite_matching() == X?"Yes":"No") << endl;
}
0