結果

問題 No.2678 Minmax Independent Set (Hack)
ユーザー NokonoKotlinNokonoKotlin
提出日時 2024-02-11 20:18:05
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,031 bytes
コンパイル時間 3,566 ms
コンパイル使用メモリ 261,952 KB
実行使用メモリ 12,068 KB
最終ジャッジ日時 2024-03-13 20:49:04
合計ジャッジ時間 4,281 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>


struct RNG {
    void setSeed(uint64_t seed) {
        seedSet = true;
        x = seed;
    }

    template <class T>
    T choice(std::vector<T>& v) {
        assert(!v.empty());
        return v[range(0, (int)v.size() - 1)];
    }

    template <class T>
    void shuffle(std::vector<T>& v) {
        const int N = v.size();
        for (int i = 0; i < N - 1; i++) {
            const int j = range(i, N - 1);
            if (i == j) continue;
            std::swap(v[i], v[j]);
        }
    }

    // generate random integers in [from, to]
    template <class T, class U>
    typename std::common_type<T, U>::type range(T from, U to) {
        static_assert(std::is_integral_v<T>);
        static_assert(std::is_integral_v<U>);
        static_assert(std::is_integral_v<typename std::common_type<T, U>::type>);

        assert(from <= to);

        uint64_t width = to - from + 1;

        typename std::common_type<T, U>::type ret = from;
        ret += xorshift64() % width;

        return ret;
    }

   private:
    bool seedSet = false;
    uint64_t x;

    uint64_t xorshift64() {
        assert(seedSet);
        x ^= x << 13;
        x ^= x >> 7;
        x ^= x << 17;
        return x;
    }
} rng;


// 辺を 1 箇所張り替えて非連結にする

using namespace std;
//----NokonoKotlin library : UnionFind(n) , nは要素数-----
class UnionFind {
   private:
    vector<long long> par;

   public:
    int Size;
    vector<long long> rank;  // rankが高いほど上の親である
    vector<long long> size;

    // 配列の中身は0 ~ N-1
    UnionFind() {}
    UnionFind(long long N) : rank(N), size(N) {
        Size = N;
        par.resize(N);
        for (int i = 0; i < Size; i++) par[i] = i;
        for (int i = 0; i < Size; i++) rank[i] = 0;
        for (int i = 0; i < Size; i++) size[i] = 1;
    }
    ~UnionFind() {
        Release();
    }

    void Release() {
        if (par.size() == 0) {
            return;
        }
    }

    int root(int x) {
        if (par[x] == x)
            return x;
        else {
            par[x] = root(par[x]);
            return par[x];
        }
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        int S = size[ry] + size[rx];
        if (rx == ry) return;
        if (rank[rx] < rank[ry]) {
            par[rx] = ry;  // rankの高い方を親にする
            size[rx] = S;
            size[ry] = S;
        } else {
            par[ry] = rx;
            size[ry] = S;
            size[rx] = S;
            if (rank[rx] == rank[ry]) rank[rx]++;
        }
    }

    int getsize(int x) {
        return size[root(x)];
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(int argc, char* argv[]) {
    rng.setSeed(372864312);

    int N = 100000;
    vector<pair<int, int>> edges;
    vector<int> prufer(N - 1);
    for (int i = 0; i < N - 2; i++) prufer[i] = rng.range(1, N - 1);
    prufer.back() = N;

    multiset<int> cands;
    for (int x = 1; x <= N; x++) cands.insert(x);
    for (int x : prufer) cands.erase(x);

    vector<int> cnt(N + 1, 0);
    for (int x : prufer) cnt[x]++;

    for (int x : prufer) {
        int child = *cands.begin();
        edges.emplace_back(x, child);
        cands.erase(child);
        cnt[x]--;
        if (cnt[x] == 0) cands.insert(x);
    }
    UnionFind T(N + 1);

    // どこかで切って 2 つの連結成分にする
    edges.erase(edges.begin() + int(edges.size()) / 2);
    for (auto p : edges) T.unite(p.first, p.second);

    cout << N << endl;
    // 片方をなもりグラフにして終了
    for (int x = 1; x < N; x++) {
        for (int y = x + 1; y <= N; y++) {
            if (T.same(x, y)) {
                edges.emplace_back(x, y);
                for (pair<int, int> p : edges) cout << min(p.first, p.second) << " " << max(p.first, p.second) << "\n";
                return 0;
            }
        }
    }

    return 0;
}
0