#520035 (C++17) No.3071 玉虫色着色

提出ソース

結果

問題	No.3071 玉虫色着色
ユーザー	Pachicobue
提出日時	2020-07-28 23:02:35
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	47 ms / 2,000 ms
コード長	9,875 bytes
コンパイル時間	3,729 ms
コンパイル使用メモリ	232,016 KB
実行使用メモリ	5,376 KB
最終ジャッジ日時	2024-07-19 16:37:58
合計ジャッジ時間	14,824 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	47 ms 5,248 KB
testcase_01	AC	9 ms 5,376 KB
testcase_02	AC	10 ms 5,376 KB
testcase_03	AC	12 ms 5,376 KB
testcase_04	AC	10 ms 5,376 KB
testcase_05	AC	9 ms 5,376 KB
testcase_06	AC	9 ms 5,376 KB
testcase_07	AC	21 ms 5,376 KB
testcase_08	AC	21 ms 5,376 KB
testcase_09	AC	22 ms 5,376 KB
testcase_10	AC	21 ms 5,376 KB
testcase_11	AC	21 ms 5,376 KB
testcase_12	AC	2 ms 5,376 KB
testcase_13	AC	2 ms 5,376 KB
testcase_14	AC	2 ms 5,376 KB
evil_large1.txt	AC	644 ms 19,824 KB
evil_large2.txt	AC	337 ms 22,020 KB

権限があれば一括ダウンロードができます

コンパイルメッセージ

main.cpp: In instantiation of 'void flow<T>::add_edge(int, int, capacity_type) [with T = int; capacity_type = int]':
main.cpp:204:49:   required from here
main.cpp:115:117: warning: narrowing conversion of '(&((flow<int>*)this)->flow<int>::edges.std::vector<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >, std::allocator<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> > > >::operator[](((std::vector<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >, std::allocator<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> > > >::size_type)((int)to))))->std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >::size()' from 'std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  115 |     void add_edge(const int from, const int to, const capacity_type cap) { edges[from].push_back({to, edges[to].size(), cap, false}), edges[to].push_back({from, edges[from].size() - 1, 0, true}); }
      |                                                                                                       ~~~~~~~~~~~~~~^~
main.cpp:115:181: warning: narrowing conversion of '((&((flow<int>*)this)->flow<int>::edges.std::vector<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >, std::allocator<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> > > >::operator[](((std::vector<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >, std::allocator<std::vector<flow<int>::edge, std::allocator<flow<int>::edge> > > >::size_type)((int)from))))->std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >::size() - 1)' from 'std::vector<flow<int>::edge, std::allocator<flow<int>::edge> >::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
  115 |     void add_edge(const int from, const int to, const capacity_type cap) { edges[from].push_back({to, edges[to].size(), cap, false}), edges[to].push_back({from, edges[from].size() - 1, 0, true}); }

ソースコード

raw source code

#include <bits/stdc++.h>

using ll                            = long long;
using uint                          = unsigned int;
using ull                           = unsigned long long;
using ld                            = long double;
template<typename T> using max_heap = std::priority_queue<T>;
template<typename T> using min_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
constexpr int popcount(const ull v) { return v ? __builtin_popcountll(v) : 0; }
constexpr int log2p1(const ull v) { return v ? 64 - __builtin_clzll(v) : 0; }
constexpr int lsbp1(const ull v) { return __builtin_ffsll(v); }
constexpr int clog(const ull v) { return v ? log2p1(v - 1) : 0; }
constexpr ull ceil2(const ull v) { return 1ULL << clog(v); }
constexpr ull floor2(const ull v) { return v ? (1ULL << (log2p1(v) - 1)) : 0ULL; }
constexpr bool btest(const ull mask, const int ind) { return (mask >> ind) & 1ULL; }
template<typename T> void bset(T& mask, const int ind) { mask |= ((T)1 << ind); }
template<typename T> void breset(T& mask, const int ind) { mask &= ~((T)1 << ind); }
template<typename T> void bflip(T& mask, const int ind) { mask ^= ((T)1 << ind); }
template<typename T> void bset(T& mask, const int ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); }
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }

template<typename T> constexpr T inf_v      = std::numeric_limits<T>::max() / 4;
template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};
constexpr ull TEN(const int n) { return n == 0 ? 1ULL : TEN(n - 1) * 10ULL; }
template<typename F> struct fix : F
{
    fix(F&& f) : F{std::forward<F>(f)} {}
    template<typename... Args> auto operator()(Args&&... args) const { return F::operator()(*this, std::forward<Args>(args)...); }
};
template<typename T, int n, int i = 0>
auto nd_array(int const (&szs)[n], const T x = T{})
{
    if constexpr (i == n) {
        return x;
    } else {
        return std::vector(szs[i], nd_array<T, n, i + 1>(szs, x));
    }
}
class printer
{
public:
    printer(std::ostream& os_ = std::cout) : os{os_} { os << std::fixed << std::setprecision(15); }
    template<typename T> int operator()(const T& v) { return os << v, 0; }
    template<typename T> int operator()(const std::vector<T>& vs)
    {
        for (int i = 0; i < (int)vs.size(); i++) { os << (i ? " " : ""), this->operator()(vs[i]); }
        return 0;
    }
    template<typename T> int operator()(const std::vector<std::vector<T>>& vss)
    {
        for (int i = 0; i < (int)vss.size(); i++) { os << (0 <= i or i + 1 < (int)vss.size() ? "\n" : ""), this->operator()(vss[i]); }
        return 0;
    }
    template<typename T, typename... Args> int operator()(const T& v, const Args&... args) { return this->operator()(v), os << ' ', this->operator()(args...), 0; }
    template<typename... Args> int ln(const Args&... args) { return this->operator()(args...), os << '\n', 0; }
    template<typename... Args> int el(const Args&... args) { return this->operator()(args...), os << std::endl, 0; }
    template<typename... Args> int fmt(const std::string& s, const Args&... args) { return rec(s, 0, args...); }

private:
    int rec(const std::string& s, int index) { return os << s.substr(index, s.size()), 0; }
    template<typename T, typename... Args> int rec(const std::string& s, int index, const T& v, const Args&... args) { return index == s.size() ? 0 : s[index] == '%' ? (this->operator()(v), rec(s, index + 1, args...)) : (os << s[index], rec(s, index + 1, v, args...)); }
    std::ostream& os;
};
printer out;

class scanner
{
public:
    scanner(std::istream& is_ = std::cin) : is{is_} { is.tie(nullptr), std::ios::sync_with_stdio(false); }
    template<typename T> T val()
    {
        static T v;
        return is >> v, v;
    }
    template<typename T> T val(const T offset) { return val<T>() - offset; }
    template<typename T> std::vector<T> vec(const int n)
    {
        std::vector<T> vs(n);
        for (auto& v : vs) { is = val<T>(); }
        return vs;
    }
    template<typename T> std::vector<T> vec(const int n, const T offset)
    {
        std::vector<T> vs(n);
        for (auto& v : vs) { is = val<T>(offset); }
        return vs;
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1)
    {
        std::vector<std::vector<T>> vss(n0);
        for (auto& vs : vss) { vs = vec<T>(n1); }
        return vss;
    }
    template<typename T> std::vector<std::vector<T>> vvec(const int n0, const int n1, const T offset)
    {
        std::vector<std::vector<T>> vss(n0);
        for (auto& vs : vss) { vs = vec<T>(n1, offset); }
        return vss;
    }
    template<typename... Args> auto tup() { return std::tuple<std::decay_t<Args>...>{val<Args>()...}; }
    template<typename... Args> auto tup(const Args&... offsets) { return std::tuple<std::decay_t<Args>...>{val<Args>(offsets)...}; }

private:
    std::istream& is;
};
scanner in;
#    define SHOW(...) static_cast<void>(0)

template<typename T>
struct flow
{
    using capacity_type = T;
    flow(const int v) : sz(v), edges(v) {}
    void add_edge(const int from, const int to, const capacity_type cap) { edges[from].push_back({to, edges[to].size(), cap, false}), edges[to].push_back({from, edges[from].size() - 1, 0, true}); }
    struct edge
    {
        int to, rev;
        capacity_type cap;
        const bool is_rev;
    };
    const std::vector<edge>& operator[](const int i) const { return edges[i]; }
    std::vector<edge>& operator[](const int i) { return edges[i]; }
    friend std::ostream& operator<<(std::ostream& os, const flow& f)
    {
        os << "[\n";
        for (int i = 0; i < f.size(); i++) {
            for (const auto& e : f[i]) {
                if (not e.is_rev) { os << i << "->" << e.to << ":"
                                       << e.cap << "\n"; }
            }
        }
        return (os << "]\n");
    }
    int size() const { return sz; }

private:
    const int sz;
    std::vector<std::vector<edge>> edges;
};
template<typename T>
T dinic(flow<T>& flow, const int s, const int t, const T max_cap = inf_v<T>)
{
    const int sz = flow.size();
    std::vector<int> level(sz, sz), iter(sz, 0);
    auto bfs = [&, sz](const T base) {
        std::fill(level.begin(), level.end(), sz);
        std::queue<int> q;
        q.push(s), level[s] = 0;
        while (not q.empty()) {
            const int s = q.front();
            q.pop();
            for (const auto& e : flow[s]) {
                if (e.cap < base or level[e.to] != sz) { continue; }
                level[e.to] = level[s] + 1, q.push(e.to);
            }
        }
    };
    auto dfs = [&, sz](auto&& self, const int s, const T base, const T f) -> T {
        if (s == t) { return f; }
        T ans = 0;
        for (int& i = iter[s]; i < flow[s].size(); i++) {
            auto& e = flow[s][i];
            if (e.cap < base or level[e.to] == sz or level[s] >= level[e.to]) { continue; }
            const T d = self(self, e.to, base, std::min(f - ans, e.cap));
            if (d == 0) { continue; }
            e.cap -= d, flow[e.to][e.rev].cap += d, ans += d;
            if (f - ans < base) { break; }
        }
        return ans;
    };
    T f = 0;
    for (T base = floor2(max_cap); base >= 1;) {
        bfs(base);
        if (level[t] == sz) {
            base >>= 1;
            continue;
        }
        std::fill(iter.begin(), iter.end(), 0);
        const T df = dfs(dfs, s, base, inf_v<T>);
        f += df;
    }
    return f;
}
int main()
{
    const auto [L, R, M] = in.tup<int, int, int>();
    std::vector<int> as(M), bs(M);
    using pii = std::pair<int, int>;
    std::multimap<pii, int> mp;
    std::vector<int> ds(L + R, 0);
    for (int i = 0; i < M; i++) {
        std::tie(as[i], bs[i]) = in.tup<int, int>(0, -L);
        ds[as[i]]++, ds[bs[i]]++;
        mp.insert({{as[i], bs[i]}, i});
    }
    const int K = *std::min_element(ds.begin(), ds.end());
    std::vector<int> ans(M, -1);
    std::set<int> es;
    for (int i = 0; i < M; i++) { es.insert(i); }
    for (int k = 0; k < K; k++) {
        flow<int> f(L + R + 2);
        const int S = L + R, T = L + R + 1;
        for (int i = 0; i < L; i++) { f.add_edge(S, i, 1); }
        for (int i = 0; i < R; i++) { f.add_edge(i + L, T, 1); }
        for (const int e : es) {
            const int a = as[e], b = bs[e];
            f.add_edge(a, b, 1);
        }
        dinic(f, S, T);
        for (int i = 0; i < L; i++) {
            bool matched = false;
            for (const auto& e : f[i]) {
                const int to = e.to;
                if (e.is_rev) { continue; }
                if (to == S or to == T) { continue; }
                if (e.cap == 0) {
                    matched      = true;
                    const int ei = mp.find({i, to})->second;
                    mp.erase(mp.find({i, to}));
                    ans[ei] = k;
                    ds[i]--, ds[to]--;
                    es.erase(ei);
                }
            }
            if (not matched) {
                int maxto = -1, max = -1;
                for (const auto& e : f[i]) {
                    const int to = e.to;
                    if (to == S or to == T) { continue; }
                    if (e.cap == 1) {
                        if (chmax(max, ds[to])) { maxto = to; }
                    }
                }
                const int ei = mp.find({i, maxto})->second;
                mp.erase(mp.find({i, maxto}));
                ds[i]--, ds[maxto]--;
                ans[ei] = k;
                es.erase(ei);
            }
        }
    }
    for (const int e : es) { ans[e] = 0; }
    out.ln(K);
    for (const int an : ans) { out.ln(an); }

    return 0;
}

yukicoder

結果

テストケース

コンパイルメッセージ

ソースコード