#712709 (C++23) No.1615 Double Down

提出ソース

結果

問題	No.1615 Double Down
ユーザー	hitonanode
提出日時	2021-11-03 21:55:03
言語	C++23 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	1,155 ms / 10,000 ms
コード長	14,467 bytes
コンパイル時間	2,367 ms
コンパイル使用メモリ	142,044 KB
実行使用メモリ	15,224 KB
最終ジャッジ日時	2024-10-13 13:30:32
合計ジャッジ時間	28,045 ms
ジャッジサーバーID （参考情報）	judge5 / judge3

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

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	346 ms 9,736 KB
testcase_01	AC	345 ms 9,584 KB
testcase_02	AC	445 ms 11,676 KB
testcase_03	AC	459 ms 11,756 KB
testcase_04	AC	445 ms 11,652 KB
testcase_05	AC	452 ms 11,692 KB
testcase_06	AC	622 ms 14,320 KB
testcase_07	AC	609 ms 14,104 KB
testcase_08	AC	618 ms 14,196 KB
testcase_09	AC	784 ms 12,564 KB
testcase_10	AC	801 ms 12,552 KB
testcase_11	AC	792 ms 12,536 KB
testcase_12	AC	893 ms 13,660 KB
testcase_13	AC	885 ms 13,668 KB
testcase_14	AC	874 ms 13,664 KB
testcase_15	AC	1,155 ms 15,208 KB
testcase_16	AC	1,099 ms 15,216 KB
testcase_17	AC	1,110 ms 15,224 KB
testcase_18	AC	964 ms 12,524 KB
testcase_19	AC	968 ms 12,584 KB
testcase_20	AC	994 ms 12,336 KB
testcase_21	AC	926 ms 12,608 KB
testcase_22	AC	929 ms 12,564 KB
testcase_23	AC	925 ms 12,692 KB
testcase_24	AC	851 ms 12,636 KB
testcase_25	AC	855 ms 12,636 KB
testcase_26	AC	880 ms 12,580 KB
testcase_27	AC	64 ms 5,248 KB
testcase_28	AC	65 ms 5,248 KB
testcase_29	AC	105 ms 5,812 KB
testcase_30	AC	106 ms 5,568 KB
testcase_31	AC	126 ms 5,608 KB
testcase_32	AC	126 ms 5,552 KB
testcase_33	AC	191 ms 6,408 KB
testcase_34	AC	195 ms 6,364 KB
testcase_35	AC	196 ms 6,316 KB
testcase_36	AC	5 ms 5,248 KB
testcase_37	AC	5 ms 5,248 KB
testcase_38	AC	6 ms 5,248 KB
testcase_39	AC	7 ms 5,248 KB
testcase_40	AC	7 ms 5,248 KB
testcase_41	AC	7 ms 5,248 KB
testcase_42	AC	10 ms 5,248 KB
testcase_43	AC	10 ms 5,248 KB
testcase_44	AC	11 ms 5,248 KB
testcase_45	AC	2 ms 5,248 KB
testcase_46	AC	2 ms 5,248 KB
testcase_47	AC	2 ms 5,248 KB
testcase_48	AC	2 ms 5,248 KB
testcase_49	AC	2 ms 5,248 KB
testcase_50	AC	2 ms 5,248 KB
testcase_51	AC	2 ms 5,248 KB
testcase_52	AC	2 ms 5,248 KB
testcase_53	AC	2 ms 5,248 KB
testcase_54	AC	2 ms 5,248 KB
testcase_55	AC	2 ms 5,248 KB
testcase_56	AC	2 ms 5,248 KB

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

ソースコード

raw source code

#line 1 "graph/test/dulmage_mendelsohn.yuki1615.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1615"
#line 2 "graph/bipartite_matching.hpp"
#include <cassert>
#include <iostream>
#include <vector>

// Bipartite matching of undirected bipartite graph (Hopcroft-Karp)
// https://ei1333.github.io/luzhiled/snippets/graph/hopcroft-karp.html
// Comprexity: O((V + E)sqrtV)
// int solve(): enumerate maximum number of matching / return -1 (if graph is not bipartite)
struct BipartiteMatching {
    int V;
    std::vector<std::vector<int>> to; // Adjacency list
    std::vector<int> dist;            // dist[i] = (Distance from i'th node)
    std::vector<int> match;           // match[i] = (Partner of i'th node) or -1 (No parter)
    std::vector<int> used, vv;
    std::vector<int> color; // color of each node(checking bipartition): 0/1/-1(not determined)

    BipartiteMatching() = default;
    BipartiteMatching(int V_) : V(V_), to(V_), match(V_, -1), used(V_), color(V_, -1) {}

    void add_edge(int u, int v) {
        assert(u >= 0 and u < V and v >= 0 and v < V and u != v);
        to[u].push_back(v);
        to[v].push_back(u);
    }

    void _bfs() {
        dist.assign(V, -1);
        std::vector<int> q;
        int lq = 0;
        for (int i = 0; i < V; i++) {
            if (!color[i] and !used[i]) q.push_back(i), dist[i] = 0;
        }

        while (lq < int(q.size())) {
            int now = q[lq++];
            for (auto nxt : to[now]) {
                int c = match[nxt];
                if (c >= 0 and dist[c] == -1) q.push_back(c), dist[c] = dist[now] + 1;
            }
        }
    }

    bool _dfs(int now) {
        vv[now] = true;
        for (auto nxt : to[now]) {
            int c = match[nxt];
            if (c < 0 or (!vv[c] and dist[c] == dist[now] + 1 and _dfs(c))) {
                match[nxt] = now, match[now] = nxt;
                used[now] = true;
                return true;
            }
        }
        return false;
    }

    bool _color_bfs(int root) {
        color[root] = 0;
        std::vector<int> q{root};
        int lq = 0;
        while (lq < int(q.size())) {
            int now = q[lq++], c = color[now];
            for (auto nxt : to[now]) {
                if (color[nxt] == -1) {
                    color[nxt] = !c, q.push_back(nxt);
                } else if (color[nxt] == c) {
                    return false;
                }
            }
        }
        return true;
    }

    int solve() {
        for (int i = 0; i < V; i++) {
            if (color[i] == -1 and !_color_bfs(i)) return -1;
        }
        int ret = 0;
        while (true) {
            _bfs();
            vv.assign(V, false);
            int flow = 0;
            for (int i = 0; i < V; i++) {
                if (!color[i] and !used[i] and _dfs(i)) flow++;
            }
            if (!flow) break;
            ret += flow;
        }
        return ret;
    }

    template <class OStream> friend OStream &operator<<(OStream &os, const BipartiteMatching &bm) {
        os << "{N=" << bm.V << ':';
        for (int i = 0; i < bm.V; i++) {
            if (bm.match[i] > i) os << '(' << i << '-' << bm.match[i] << "),";
        }
        return os << '}';
    }
};
#line 2 "graph/strongly_connected_components.hpp"
#include <algorithm>
#line 5 "graph/strongly_connected_components.hpp"

// CUT begin
// Directed graph library to find strongly connected components （強連結成分分解）
// 0-indexed directed graph
// Complexity: O(V + E)
struct DirectedGraphSCC {
    int V; // # of Vertices
    std::vector<std::vector<int>> to, from;
    std::vector<int> used; // Only true/false
    std::vector<int> vs;
    std::vector<int> cmp;
    int scc_num = -1;

    DirectedGraphSCC(int V = 0) : V(V), to(V), from(V), cmp(V) {}

    void _dfs(int v) {
        used[v] = true;
        for (auto t : to[v])
            if (!used[t]) _dfs(t);
        vs.push_back(v);
    }
    void _rdfs(int v, int k) {
        used[v] = true;
        cmp[v] = k;
        for (auto t : from[v])
            if (!used[t]) _rdfs(t, k);
    }

    void add_edge(int from_, int to_) {
        assert(from_ >= 0 and from_ < V and to_ >= 0 and to_ < V);
        to[from_].push_back(to_);
        from[to_].push_back(from_);
    }

    // Detect strongly connected components and return # of them.
    // Also, assign each vertex `v` the scc id `cmp[v]` (0-indexed)
    int FindStronglyConnectedComponents() {
        used.assign(V, false);
        vs.clear();
        for (int v = 0; v < V; v++)
            if (!used[v]) _dfs(v);
        used.assign(V, false);
        scc_num = 0;
        for (int i = (int)vs.size() - 1; i >= 0; i--)
            if (!used[vs[i]]) _rdfs(vs[i], scc_num++);
        return scc_num;
    }

    // Find and output the vertices that form a closed cycle.
    // output: {v_1, ..., v_C}, where C is the length of cycle,
    //         {} if there's NO cycle (graph is DAG)
    int _c, _init;
    std::vector<int> _ret_cycle;
    bool _dfs_detectcycle(int now, bool b0) {
        if (now == _init and b0) return true;
        for (auto nxt : to[now])
            if (cmp[nxt] == _c and !used[nxt]) {
                _ret_cycle.emplace_back(nxt), used[nxt] = 1;
                if (_dfs_detectcycle(nxt, true)) return true;
                _ret_cycle.pop_back();
            }
        return false;
    }
    std::vector<int> DetectCycle() {
        int ns = FindStronglyConnectedComponents();
        if (ns == V) return {};
        std::vector<int> cnt(ns);
        for (auto x : cmp) cnt[x]++;
        _c = std::find_if(cnt.begin(), cnt.end(), [](int x) { return x > 1; }) - cnt.begin();
        _init = std::find(cmp.begin(), cmp.end(), _c) - cmp.begin();
        used.assign(V, false);
        _ret_cycle.clear();
        _dfs_detectcycle(_init, false);
        return _ret_cycle;
    }

    // After calling `FindStronglyConnectedComponents()`, generate a new graph by uniting all vertices
    // belonging to the same component(The resultant graph is DAG).
    DirectedGraphSCC GenerateTopologicalGraph() {
        DirectedGraphSCC newgraph(scc_num);
        for (int s = 0; s < V; s++)
            for (auto t : to[s]) {
                if (cmp[s] != cmp[t]) newgraph.add_edge(cmp[s], cmp[t]);
            }
        return newgraph;
    }
};

// 2-SAT solver: Find a solution for  `(Ai v Aj) ^ (Ak v Al) ^ ... = true`
// - `nb_sat_vars`: Number of variables
// - Considering a graph with `2 * nb_sat_vars` vertices
// - Vertices [0, nb_sat_vars) means `Ai`
// - vertices [nb_sat_vars, 2 * nb_sat_vars) means `not Ai`
struct SATSolver : DirectedGraphSCC {
    int nb_sat_vars;
    std::vector<int> solution;
    SATSolver(int nb_variables = 0) : DirectedGraphSCC(nb_variables * 2), nb_sat_vars(nb_variables), solution(nb_sat_vars) {}
    void add_x_or_y_constraint(bool is_x_true, int x, bool is_y_true, int y) {
        assert(x >= 0 and x < nb_sat_vars);
        assert(y >= 0 and y < nb_sat_vars);
        if (!is_x_true) x += nb_sat_vars;
        if (!is_y_true) y += nb_sat_vars;
        add_edge((x + nb_sat_vars) % (nb_sat_vars * 2), y);
        add_edge((y + nb_sat_vars) % (nb_sat_vars * 2), x);
    }
    // Solve the 2-SAT problem. If no solution exists, return `false`.
    // Otherwise, dump one solution to `solution` and return `true`.
    bool run() {
        FindStronglyConnectedComponents();
        for (int i = 0; i < nb_sat_vars; i++) {
            if (cmp[i] == cmp[i + nb_sat_vars]) return false;
            solution[i] = cmp[i] > cmp[i + nb_sat_vars];
        }
        return true;
    }
};
#line 5 "graph/dulmage_mendelsohn_decomposition.hpp"
#include <utility>
#line 7 "graph/dulmage_mendelsohn_decomposition.hpp"

// Dulmage–Mendelsohn (DM) decomposition （DM 分解）
// return: [(W+0, W-0), (W+1,W-1),...,(W+(k+1), W-(k+1))]
//         : sequence of pair (left vetrices, right vertices)
//         - |W+0| < |W-0| or both empty
//         - |W+i| = |W-i| (i = 1, ..., k)
//         - |W+(k+1)| > |W-(k+1)| or both empty
//         - W is topologically sorted
// Example:
// (2, 2, [(0,0), (0,1), (1,0)]) => [([],[]),([0,],[1,]),([1,],[0,]),([],[]),]
// Complexity: O(N + (N + M) sqrt(N))
// Verified: https://yukicoder.me/problems/no/1615
std::vector<std::pair<std::vector<int>, std::vector<int>>>
dulmage_mendelsohn(int L, int R, const std::vector<std::pair<int, int>> &edges) {
    for (auto p : edges) {
        assert(0 <= p.first and p.first < L);
        assert(0 <= p.second and p.second < R);
    }

    BipartiteMatching bm(L + R);
    for (auto p : edges) bm.add_edge(p.first, L + p.second);
    bm.solve();

    DirectedGraphSCC scc(L + R);
    for (auto p : edges) scc.add_edge(p.first, L + p.second);
    for (int l = 0; l < L; ++l) {
        if (bm.match[l] >= L) scc.add_edge(bm.match[l], l);
    }

    int nscc = scc.FindStronglyConnectedComponents();
    std::vector<int> cmp_map(nscc, -2);

    std::vector<int> vis(L + R);
    std::vector<int> st;
    for (int c = 0; c < 2; ++c) {
        std::vector<std::vector<int>> to(L + R);
        auto color = [&L](int x) { return x >= L; };
        for (auto p : edges) {
            int u = p.first, v = L + p.second;
            if (color(u) != c) std::swap(u, v);
            to[u].push_back(v);
            if (bm.match[u] == v) to[v].push_back(u);
        }
        for (int i = 0; i < L + R; ++i) {
            if (bm.match[i] >= 0 or color(i) != c or vis[i]) continue;
            vis[i] = 1, st = {i};
            while (!st.empty()) {
                int now = st.back();
                cmp_map[scc.cmp[now]] = c - 1;
                st.pop_back();
                for (int nxt : to[now]) {
                    if (!vis[nxt]) vis[nxt] = 1, st.push_back(nxt);
                }
            }
        }
    }

    int nset = 1;
    for (int n = 0; n < nscc; ++n) {
        if (cmp_map[n] == -2) cmp_map[n] = nset++;
    }
    for (auto &x : cmp_map) {
        if (x == -1) x = nset;
    }
    nset++;

    std::vector<std::pair<std::vector<int>, std::vector<int>>> groups(nset);

    for (int l = 0; l < L; ++l) {
        if (bm.match[l] < 0) continue;
        int c = cmp_map[scc.cmp[l]];
        groups[c].first.push_back(l);
        groups[c].second.push_back(bm.match[l] - L);
    }
    for (int l = 0; l < L; ++l) {
        if (bm.match[l] >= 0) continue;
        int c = cmp_map[scc.cmp[l]];
        groups[c].first.push_back(l);
    }
    for (int r = 0; r < R; ++r) {
        if (bm.match[L + r] >= 0) continue;
        int c = cmp_map[scc.cmp[L + r]];
        groups[c].second.push_back(r);
    }

    return groups;
}
#line 6 "graph/test/dulmage_mendelsohn.yuki1615.test.cpp"
#include <set>
#line 9 "graph/test/dulmage_mendelsohn.yuki1615.test.cpp"
using namespace std;

std::vector<std::pair<std::vector<int>, std::vector<int>>>
verify_dulmage_mendelsohn(int L, int R, const std::vector<std::pair<int, int>> &edges) {
    auto ret = dulmage_mendelsohn(L, R, edges);
    assert(ret.size() >= 2);
    vector<int> lord(L, -1), rord(R, -1);
    set<pair<int, int>> edges_set(edges.begin(), edges.end());

    for (int igrp = 0; igrp < int(ret.size()); ++igrp) {
        for (int vl : ret[igrp].first) {
            assert(lord[vl] < 0);
            lord[vl] = igrp;
        }
        for (int vr : ret[igrp].second) {
            assert(rord[vr] < 0);
            rord[vr] = igrp;
        }
        if (igrp == 0) {
            assert(ret[igrp].first.size() < ret[igrp].second.size() or ret[igrp].first.empty());
        } else if (igrp + 1 == int(ret.size())) {
            assert(ret[igrp].first.size() > ret[igrp].second.size() or ret[igrp].second.empty());
        } else {
            assert(ret[igrp].first.size() == ret[igrp].second.size());
            assert(ret[igrp].first.size());
        }
        for (int j = 0; j < min<int>(ret[igrp].first.size(), ret[igrp].second.size()); ++j) {
            auto u = ret[igrp].first[j], v = ret[igrp].second[j];
            assert(edges_set.count(make_pair(u, v)));
        }
    }
    assert(count(lord.begin(), lord.end(), -1) == 0);
    assert(count(rord.begin(), rord.end(), -1) == 0);

    for (auto e : edges) {
        assert(0 <= e.first and e.first < L);
        assert(0 <= e.second and e.second < R);
        assert(lord.at(e.first) <= rord.at(e.second)); // Check topological order
    }
    return ret;
}

int main() {
    cin.tie(nullptr), ios::sync_with_stdio(false);

    int N, M, K, L;
    cin >> N >> M >> K >> L;
    vector<vector<pair<int, int>>> z2xy(K + 1);

    while (L--) {
        int x, y, z;
        cin >> x >> y >> z;
        x--, y--;
        z2xy[K - z].emplace_back(x, y);
    }
    vector<int> vtp(N + M, 3);

    vector<pair<int, int>> alive_edges;

    long long ret = 0;
    int nmatch = 0;

    vector<int> experience12(N + M);
    vector<int> fixed_pair(N, -1);

    for (const auto &xys : z2xy) {
        for (auto p : xys) {
            int u = p.first, v = p.second;
            if (experience12[u] or experience12[N + v]) continue;
            alive_edges.emplace_back(u, v);
        }

        auto dm_ret = verify_dulmage_mendelsohn(N, M, alive_edges);

        int nmatchnxt = 0;
        for (const auto &p : dm_ret) nmatchnxt += min(p.first.size(), p.second.size());

        ret = ret * 2 + nmatchnxt - nmatch;

        for (auto l : dm_ret.front().first) vtp[l] = 2, experience12[l] = 1;
        for (auto r : dm_ret.front().second) vtp[r + N] = 3;
        for (auto l : dm_ret.back().first) vtp[l] = 3;
        for (auto r : dm_ret.back().second) vtp[r + N] = 2, experience12[r + N] = 1;

        for (int i = 1; i + 1 < int(dm_ret.size()); ++i) {
            for (int j = 0; j < int(dm_ret[i].first.size()); ++j) {
                int l = dm_ret[i].first[j], r = dm_ret[i].second[j];
                if (fixed_pair[l] < 0) {
                    vtp[l] = vtp[r + N] = 1, fixed_pair[l] = r;
                    experience12[l] = experience12[r + N] = 1;
                    alive_edges.emplace_back(l, r);
                }
            }
        }

        for (int cur = 0; cur < int(alive_edges.size());) {
            int u = alive_edges[cur].first, v = alive_edges[cur].second;
            if (vtp[u] + vtp[v + N] == 5 or fixed_pair[u] == v) {
                cur++;
            } else {
                alive_edges[cur].swap(alive_edges.back());
                alive_edges.pop_back();
            }
        }
        nmatch = nmatchnxt;
    }
    cout << ret << endl;
}