結果

問題 No.2238 Rock and Hole
ユーザー 👑 NachiaNachia
提出日時 2023-03-03 22:18:41
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 18 ms / 3,000 ms
コード長 5,603 bytes
コンパイル時間 1,180 ms
コンパイル使用メモリ 93,148 KB
実行使用メモリ 6,712 KB
最終ジャッジ日時 2023-10-18 02:27:22
合計ジャッジ時間 2,285 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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 1 ms
4,348 KB
testcase_08 AC 2 ms
4,348 KB
testcase_09 AC 2 ms
4,348 KB
testcase_10 AC 4 ms
4,348 KB
testcase_11 AC 8 ms
5,420 KB
testcase_12 AC 7 ms
5,360 KB
testcase_13 AC 6 ms
5,304 KB
testcase_14 AC 4 ms
4,348 KB
testcase_15 AC 4 ms
4,800 KB
testcase_16 AC 7 ms
6,244 KB
testcase_17 AC 9 ms
6,712 KB
testcase_18 AC 7 ms
6,040 KB
testcase_19 AC 11 ms
4,956 KB
testcase_20 AC 12 ms
4,956 KB
testcase_21 AC 18 ms
4,976 KB
testcase_22 AC 8 ms
4,872 KB
testcase_23 AC 2 ms
4,348 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "Main.cpp"
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <atcoder/modint>
#line 2 "nachia\\array\\csr-array.hpp"
#include <utility>
#line 5 "nachia\\array\\csr-array.hpp"

namespace nachia{

template<class Elem>
class CsrArray{
public:
    struct ListRange{
        using iterator = typename std::vector<Elem>::iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        Elem& operator[](int i) const { return begi[i]; }
    };
    struct ConstListRange{
        using iterator = typename std::vector<Elem>::const_iterator;
        iterator begi, endi;
        iterator begin() const { return begi; }
        iterator end() const { return endi; }
        int size() const { return (int)std::distance(begi, endi); }
        const Elem& operator[](int i) const { return begi[i]; }
    };
private:
    int m_n;
    std::vector<Elem> m_list;
    std::vector<int> m_pos;
public:
    CsrArray() : m_n(0), m_list(), m_pos() {}
    static CsrArray Construct(int n, std::vector<std::pair<int, Elem>> items){
        CsrArray res;
        res.m_n = n;
        std::vector<int> buf(n+1, 0);
        for(auto& [u,v] : items){ ++buf[u]; }
        for(int i=1; i<=n; i++) buf[i] += buf[i-1];
        res.m_list.resize(buf[n]);
        for(int i=(int)items.size()-1; i>=0; i--){
            res.m_list[--buf[items[i].first]] = std::move(items[i].second);
        }
        res.m_pos = std::move(buf);
        return res;
    }
    static CsrArray FromRaw(std::vector<Elem> list, std::vector<int> pos){
        CsrArray res;
        res.m_n = pos.size() - 1;
        res.m_list = std::move(list);
        res.m_pos = std::move(pos);
        return res;
    }
    ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; }
    int size() const { return m_n; }
    int fullSize() const { return (int)m_list.size(); }
};

} // namespace nachia
#line 6 "nachia\\graph\\bipertite-matching.hpp"

namespace nachia{

std::vector<int> BipertiteMatching(int N1, int N2, const std::vector<std::pair<int, int>>& edges){
    std::vector<int> R(N2, -1);
    std::vector<int> L(N1, -1);
    auto E = CsrArray<int>::Construct(N1, edges);
    while(true){
        std::vector<int> bfs, dist(N1, -1), P(N1, -1);
        for(int i=0; i<N1; i++) if(L[i] == -1){ bfs.push_back(i); dist[i] = 0; }
        int maxD = N1 + 1;
        for(size_t i=0; i<bfs.size(); i++){
            int p = bfs[i];
            if(dist[p] >= maxD) break;
            for(int e : E[p]) if(L[p] != e){
                if(R[e] >= 0){
                    if(dist[R[e]] < 0){
                        dist[R[e]] = dist[p] + 1;
                        P[R[e]] = p;
                        bfs.push_back(R[e]);
                    }
                }
                else maxD = dist[p];
            }
        }
        if(maxD > N1) break;
        std::vector<int> I(N1, 0);
        for(int s=0; s<N1; s++) if(L[s] == -1){
            int p = s, p2;
            while(p >= 0){
                if(I[p] == E[p].size()){ p = P[p]; continue; }
                int q = E[p][I[p]++];
                int r = R[q];
                if(r == -1){ p2 = q; break; }
                if(dist[r] != dist[p] + 1) continue;
                P[r] = p;
                p = r;
            }
            if(p < 0) continue;
            while(p >= 0){
                R[p2] = p;
                std::swap(L[p], p2);
                p = P[p];
            }
        }
    }
    std::vector<int> ans;
    for(int i=0; i<(int)edges.size(); i++){
        auto& e = edges[i];
        if(L[e.first] == e.second){ L[e.first] = -1; ans.push_back(i); }
    }
    return ans;
}

} // namespace nachia
#line 7 "Main.cpp"
using namespace std;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
const i64 INF = 1001001001001001001;

using Modint = atcoder::static_modint<998244353>;


int main(){
    int H,W; cin >> H >> W;
    vector<string> G(H); rep(y,H) cin >> G[y];
    vector<pair<int, int>> A;
    int numH = 0, numR = 0;
    vector<vector<int>> Id(H, vector<int>(W));
    rep(y,H) rep(x,W){
        if(G[y][x] == 'h') Id[y][x] = numH++;
        if(G[y][x] == 'r') Id[y][x] = numR++;
    }
    rep(y,H){
        int f = -1;
        rep(x,W){
            if(G[y][x] == 'h') f = Id[y][x];
            if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]);
        }
        f = -1;
        for(int x=W-1; x>=0; x--){
            if(G[y][x] == 'h') f = Id[y][x];
            if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]);
        }
    }
    rep(x,W){
        int f = -1;
        rep(y,H){
            if(G[y][x] == 'h') f = Id[y][x];
            if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]);
        }
        for(int y=H-1; y>=0; y--){
            if(G[y][x] == 'h') f = Id[y][x];
            if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]);
        }
    }
    auto res = nachia::BipertiteMatching(numH, numR, A);
    int resnum = 0;
    for(auto a : res) if(a >= 0) resnum++;
    cout << (resnum == numR ? "Yes\n" : "No\n");
    return 0;
}



struct ios_do_not_sync{
    ios_do_not_sync(){
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0