#757588 (C++23) No.382 シャイな人たち (2)

• 問題: No.382 シャイな人たち (2)
• ユーザー: hitonanode
• 提出日時: 2022-05-01 18:51:20
• 言語: C++23 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 2,169 ms / 8,000 ms
• コード長: 5,757 bytes
• コンパイル時間: 1,211 ms
• コンパイル使用メモリ: 103,152 KB
• 実行使用メモリ: 6,944 KB
• 最終ジャッジ日時: 2024-06-30 20:46:04
• 合計ジャッジ時間: 40,981 ms
• ジャッジサーバーID （参考情報）: judge2 / judge3

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2,169 ms; 6,812 KB
testcase_01	AC	2,169 ms; 6,940 KB
testcase_02	AC	1,852 ms; 6,940 KB
testcase_03	AC	1,821 ms; 6,940 KB
testcase_04	AC	1,765 ms; 6,944 KB
testcase_05	AC	1,927 ms; 6,940 KB
testcase_06	AC	1,463 ms; 6,944 KB
testcase_07	AC	2,035 ms; 6,940 KB
testcase_08	AC	1,557 ms; 6,944 KB
testcase_09	AC	1,638 ms; 6,944 KB
testcase_10	AC	1,680 ms; 6,944 KB
testcase_11	AC	1,530 ms; 6,940 KB
testcase_12	AC	1,755 ms; 6,940 KB
testcase_13	AC	1,756 ms; 6,944 KB
testcase_14	AC	2,030 ms; 6,940 KB
testcase_15	AC	2,013 ms; 6,944 KB
testcase_16	AC	1,757 ms; 6,940 KB
testcase_17	AC	1,609 ms; 6,940 KB
testcase_18	AC	1,976 ms; 6,944 KB
testcase_19	AC	1,759 ms; 6,940 KB
testcase_20	AC	2 ms; 6,940 KB

ソースコード

#line 1 "graph/test/maximum_independent_set.yuki382.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/382"
#line 2 "graph/maximum_independent_set.hpp"
#include <bitset>
#include <cassert>
#include <stack>
#include <vector>

// Maximum Independent Set for general graph （最大独立集合）
// Works with reasonable time complexity when N~40
// Given graph must not have self-edges
// Verified: https://judge.yosupo.jp/submission/1864 / https://yukicoder.me/problems/no/382
// Reference: https://www.slideshare.net/wata_orz/ss-12131479
template <typename E, int BS = 64> struct MaximumIndependentSet {
    std::vector<std::bitset<BS>> conn;
    int V;               // # of vertices
    int nret;            // Largest possible size of independent set
    std::bitset<BS> ret; // Result is saved here: use (1), don't use (0)
    std::bitset<BS> _avail;
    std::bitset<BS> _tmp_state;

    void mis_dfs() {
        bool retry = true;
        std::stack<int> st;
        while (retry) {
            retry = false;
            for (int i = _avail._Find_first(); i < V; i = _avail._Find_next(i)) {
                int nb = (_avail & conn[i]).count();
                if (nb <= 1) {
                    st.emplace(i), _avail.reset(i), _tmp_state.set(i);
                    retry = true;
                    if (nb == 1) {
                        int j = (_avail & conn[i])._Find_first();
                        st.emplace(j), _avail.reset(j);
                    }
                }
            }
        }

        int t = _tmp_state.count();
        if (t > nret) nret = t, ret = _tmp_state;

        int d = -1, n = -1;
        for (int i = _avail._Find_first(); i < V; i = _avail._Find_next(i)) {
            int c = (_avail & conn[i]).count();
            if (c > d) d = c, n = i;
        }

        if (d > 0) {
            std::bitset<BS> nxt = _avail & conn[n];
            _avail.reset(n);
            mis_dfs();
            _tmp_state.set(n);
            _avail &= ~nxt;
            mis_dfs();
            _avail |= nxt;
            _avail.set(n);
            _tmp_state.reset(n);
        }

        while (st.size()) {
            int i = st.top();
            _avail.set(i);
            _tmp_state.reset(i);
            st.pop();
        }
    }
    MaximumIndependentSet(const E &e) : conn(e.size()), V(e.size()), nret(-1) {
        assert(V <= BS);
        for (int i = 0; i < V; i++)
            for (auto &j : e[i])
                if (i != j) conn[i].set(j), conn[j].set(i);
        for (int i = 0; i < V; i++) _avail.set(i);
        _tmp_state.reset();
        mis_dfs();
    }
};

// A little fast implementation of MaximumIndependentSet
// by substituting long long int's bit for `ret` & `_tmp_state`
// Requirement: V <= 64
template <typename E> struct MaximumIndependentSet_Intbased {
    std::vector<long long> conn;
    int V;         // # of vertices
    int nret;      // Largest possible size of independent set
    long long ret; // Result is saved here: use (1), don't use (0)
    long long _avail;
    long long _tmp_state;

    void mis_dfs() {
        bool retry = true;
        std::stack<int> st;
        while (retry) {
            retry = false;
            for (int i = 0; i < V; i++)
                if (_avail & (1LL << i)) {
                    int nb = __builtin_popcountll(_avail & conn[i]);
                    if (nb <= 1) {
                        st.emplace(i), _avail -= 1LL << i, _tmp_state |= 1LL << i;
                        retry = true;
                        if (nb == 1) {
                            int j = __builtin_ctzll(_avail & conn[i]);
                            st.emplace(j), _avail &= ~(1LL << j);
                        }
                    }
                }
        }

        int t = __builtin_popcountll(_tmp_state);
        if (t > nret) nret = t, ret = _tmp_state;

        int d = -1, n = -1;
        for (int i = 0; i < V; i++)
            if (_avail & (1LL << i)) {
                int c = __builtin_popcountll(_avail & conn[i]);
                if (c > d) d = c, n = i;
            }

        if (d > 0) {
            long long nxt = _avail & conn[n];
            _avail -= 1LL << n;
            mis_dfs();
            _tmp_state |= 1LL << n;
            _avail &= ~nxt;
            mis_dfs();
            _avail |= nxt;
            _avail |= 1LL << n;
            _tmp_state &= ~(1LL << n);
        }

        while (st.size()) {
            int i = st.top();
            _avail |= 1LL << i;
            _tmp_state &= ~(1LL << i);
            st.pop();
        }
    }
    MaximumIndependentSet_Intbased(const E &e)
        : conn(e.size()), V(e.size()), nret(-1), _avail((1LL << V) - 1), _tmp_state(0) {
        assert(V <= 63);
        for (int i = 0; i < V; i++)
            for (auto &j : e[i])
                if (i != j) conn[i] |= 1LL << j, conn[j] |= 1LL << i;
        mis_dfs();
    }
};
#line 3 "graph/test/maximum_independent_set.yuki382.test.cpp"
#include <iostream>
#include <string>
using namespace std;

int main() {
    int S;
    constexpr int md = 1000003;
    auto nxt = [&]() { S = S * 12345LL % md; };

    cin >> S;
    nxt();
    const int N = S % 120 + 2;
    nxt();
    const int P = S;
    std::vector<std::vector<int>> to(N);
    for (int i = 0; i < N; ++i) {
        for (int j = i + 1; j < N; ++j) {
            nxt();
            if (S >= P) to[i].push_back(j);
        }
    }
    MaximumIndependentSet<decltype(to), 121> graph(to);

    if (graph.nret == N) {
        cout << -1 << '\n';
    } else {
        cout << graph.nret + 1 << '\n';
        string ret;
        for (int i = 0; i < N; ++i) {
            if (graph.ret[i]) ret += to_string(i + 1) + " ";
        }
        ret.pop_back();
        cout << ret << '\n';
    }
}