結果
問題 | No.2238 Rock and Hole |
ユーザー | otamay6 |
提出日時 | 2023-03-03 23:32:18 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 79 ms / 3,000 ms |
コード長 | 3,093 bytes |
コンパイル時間 | 2,914 ms |
コンパイル使用メモリ | 227,108 KB |
実行使用メモリ | 15,248 KB |
最終ジャッジ日時 | 2023-10-18 03:44:11 |
合計ジャッジ時間 | 4,568 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,348 KB |
testcase_01 | AC | 2 ms
4,348 KB |
testcase_02 | AC | 2 ms
4,348 KB |
testcase_03 | AC | 2 ms
4,348 KB |
testcase_04 | AC | 2 ms
4,348 KB |
testcase_05 | AC | 2 ms
4,348 KB |
testcase_06 | AC | 2 ms
4,348 KB |
testcase_07 | AC | 2 ms
4,348 KB |
testcase_08 | AC | 2 ms
4,348 KB |
testcase_09 | AC | 2 ms
4,348 KB |
testcase_10 | AC | 7 ms
4,404 KB |
testcase_11 | AC | 43 ms
11,420 KB |
testcase_12 | AC | 56 ms
11,944 KB |
testcase_13 | AC | 39 ms
11,288 KB |
testcase_14 | AC | 19 ms
7,856 KB |
testcase_15 | AC | 7 ms
4,960 KB |
testcase_16 | AC | 79 ms
15,060 KB |
testcase_17 | AC | 72 ms
14,984 KB |
testcase_18 | AC | 69 ms
15,248 KB |
testcase_19 | AC | 31 ms
7,332 KB |
testcase_20 | AC | 37 ms
9,220 KB |
testcase_21 | AC | 32 ms
8,144 KB |
testcase_22 | AC | 32 ms
8,808 KB |
testcase_23 | AC | 2 ms
4,348 KB |
ソースコード
#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; }