結果

問題 No.1479 Matrix Eraser
コンテスト
ユーザー tonegawa
提出日時 2024-11-12 06:34:30
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 222 ms / 3,000 ms
コード長 9,542 bytes
コンパイル時間 3,327 ms
コンパイル使用メモリ 205,896 KB
実行使用メモリ 28,816 KB
最終ジャッジ日時 2024-11-12 06:34:41
合計ジャッジ時間 10,183 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In member function 'std::vector<std::pair<bool, int> > hopcroft_karp::max_independent_set()':
main.cpp:294:5: warning: no return statement in function returning non-void [-Wreturn-type]
  294 |     }
      |     ^

ソースコード

diff # 


#include <iostream>
#include <string>
#include <vector>
#include <array>
#include <tuple>
#include <stack>
#include <queue>
#include <deque>
#include <algorithm>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <cmath>
#include <functional>
#include <cassert>
#include <climits>
#include <iomanip>
#include <numeric>
#include <memory>
#include <random>
#include <thread>
#include <chrono>
#define allof(obj) (obj).begin(), (obj).end()
#define range(i, l, r) for(int i=l;i<r;i++)
#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())
#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)
#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))
#define bit_kth(i, k) ((i >> k)&1)
#define bit_highest(i) (i?63-__builtin_clzll(i):-1)
#define bit_lowest(i) (i?__builtin_ctzll(i):-1)
#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))
using ll = long long;
using ld = long double;
using ul = uint64_t;
using pi = std::pair<int, int>;
using pl = std::pair<ll, ll>;
using namespace std;

template<typename F, typename S>
std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {
    dest << p.first << ' ' << p.second;
    return dest;
}

template<typename A, typename B>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t);
    return dest;
}

template<typename A, typename B, typename C>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);
    return dest;
}

template<typename A, typename B, typename C, typename D>
std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {
    dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz; i++) {
        int m = v[i].size();
        for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');
    }
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {
    int sz = v.size();
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T, size_t sz>
std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {
    if (!sz) return dest;
    for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';
    dest << v[sz - 1];
    return dest;
}

template<typename T>
std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {
    for (auto itr = v.begin(); itr != v.end();) {
        dest << *itr;
        itr++;
        if (itr != v.end()) dest << ' ';
    }
    return dest;
}

template<typename T, typename E>
std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {
    for (auto itr = v.begin(); itr != v.end(); ) {
        dest << '(' << itr->first << ", " << itr->second << ')';
        itr++;
        if (itr != v.end()) dest << '\n';
    }
    return dest;
}

template<typename T>
vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }

template<typename T, typename... Tail>
auto make_vec(size_t sz, Tail ...tail) {
    return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));
}

template<typename T>
vector<T> read_vec(size_t sz) {
    std::vector<T> v(sz);
    for (int i = 0; i < (int)sz; i++) std::cin >> v[i];
    return v;
}

template<typename T, typename... Tail>
auto read_vec(size_t sz, Tail ...tail) {
    auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);
    for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);
    return v;
}

// x / y以上の最小の整数
ll ceil_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? y - 1 : 0)) / y;
}

// x / y以下の最大の整数
ll floor_div(ll x, ll y) {
    assert(y > 0);
    return (x + (x > 0 ? 0 : -y + 1)) / y;
}

void io_init() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
}



#include <limits>

struct hopcroft_karp {
    private:
    int N, M;
    std::vector<std::pair<int, int>> info;
    std::vector<std::vector<int>> G;

    std::vector<int> matchL, matchR;

  public:
    hopcroft_karp() : N(0), M(0) {}
    hopcroft_karp(int n, int m) : N(n), M(m), G(n), matchL(N, -1), matchR(M, -1) {}

    int add_edge(int s, int t) {
        assert(0 <= s && s < N);
        assert(0 <= t && t < M);
        int m = int(info.size());
        info.push_back({s, t});
        G[s].push_back(t);
        return m;
    }
    struct edge {
        int s, t;
        bool used;
    };

    edge get_edge(int i) {
        int m = int(info.size());
        assert(0 <= i && i < m);
        auto [s, t] = info[i];
        return edge{s, t, matchL[s] == t};
    }

    std::vector<edge> edges() {
        int M = int(info.size());
        std::vector<edge> result;
        for (int i = 0; i < M; i++) result.push_back(get_edge(i));
        return result;
    }

    int max_flow() { return max_flow(std::numeric_limits<int>::max()); }
    int max_flow(int flow_limit) {
        std::vector<int> level(N), iter(N), que(N);
        auto bfs = [&]() {
            std::fill(level.begin(), level.end(), -1);
            int l = 0, r = 0;
            for (int i = 0; i < N; i++) {
                if (matchL[i] == -1) {
                    level[i] = 0;
                    que[r++] = i;
                }
            }
            while (l < r) {
                int v = que[l++];
                for (int t : G[v]) {
                    int tt = matchR[t];
                    if (tt == -1 || level[tt] != -1) continue;
                    level[tt] = level[v] + 1;
                    que[r++] = tt;
                }
            }
        };
        auto dfs = [&](auto self, int v) -> bool {
            int level_v = level[v];
            for (int& i = iter[v]; i < int(G[v].size()); i++) {
                int t = G[v][i];
                int tt = matchR[t];
                if (tt == -1 || (level[tt] > level_v && self(self, tt))) {
                    matchR[t] = v;
                    matchL[v] = t;
                    return true;
                }
            }
            return false;
        };

        int flow = 0;
        while (flow < flow_limit) {
            bfs();
            std::fill(iter.begin(), iter.end(), 0);
            bool ok = false;
            for (int i = 0; i < N && flow < flow_limit; i++) {
                if (matchL[i] != -1) continue;
                bool f = dfs(dfs, i);
                flow += f;
                ok |= f;
            }
            if (!ok) break;
        }
        return flow;
    }

    std::vector<int> pairL() const { return matchL; }
    std::vector<int> pairR() const { return matchR; }
    std::vector<std::pair<int, int>> pairs() const {
        std::vector<std::pair<int, int>> res;
        for (int i = 0; i < N; i++) {
            if (matchL[i] != -1) {
                res.push_back({i, matchL[i]});
            }
        }
        return res;
    }

    // 点カバー (= max_flow) (max_flowを先に呼ぶ)
    // {0, i} : 左のi {1, i} := 右のi
    std::vector<std::pair<bool, int>> min_vertex_cover() {
        std::vector<bool> visitedL(N, false), visitedR(M, false);
        auto dfs = [&](auto self, int v) {
            visitedL[v] = true;
            if (matchL[v] != -1) return; 
            for (int t : G[v]) {
                visitedR[t] = true;
                if (matchR[t] == -1 || visitedL[matchR[t]]) continue;
                self(self, matchR[t]);
            }
        };
        for (int i = 0; i < N; i++) {
            if (matchL[i] == -1 && !visitedL[i]) {
                dfs(dfs, i);
            }
        }

        std::vector<std::pair<bool, int>> res;
        for (int i = 0; i < N; i++) {
            if (!visitedL[i]) res.push_back({0, i});
        }
        for (int i = 0; i < M; i++) {
            if (visitedR[i]) res.push_back({1, i});
        }
        return res;
    }

    // 最大独立集合 (= (N + M) - max_flow) (max_flowを先に呼ぶ)
    // {0, i} : 左のi {1, i} := 右のi
    std::vector<std::pair<bool, int>> max_independent_set() {
        //
    }
};


int main() {
    io_init();
    int H, W;
    std::cin >> H >> W;
    auto A = read_vec<int>(H, W);

    std::vector<std::pair<int, int>> R, C;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (A[i][j] == 0) continue;
            R.push_back({i, A[i][j]});
            C.push_back({j, A[i][j]});
        }
    }

    sort(allof(R));
    R.erase(unique(allof(R)), R.end());
    sort(allof(C));
    C.erase(unique(allof(C)), C.end());

    hopcroft_karp G(R.size(), C.size());
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (A[i][j] == 0) continue;
            int idx1 = std::lower_bound(allof(R), std::pair<int, int>{i, A[i][j]}) - R.begin();
            int idx2 = std::lower_bound(allof(C), std::pair<int, int>{j, A[i][j]}) - C.begin();
            G.add_edge(idx1, idx2);
        }
    }
    int f = G.max_flow();
    assert(f == G.min_vertex_cover().size());
    std::cout << f << '\n';
}
0