結果

問題 No.2678 Minmax Independent Set (Hack)
ユーザー NokonoKotlinNokonoKotlin
提出日時 2024-02-11 20:18:46
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 2,436 bytes
コンパイル時間 3,213 ms
コンパイル使用メモリ 255,000 KB
実行使用メモリ 7,048 KB
最終ジャッジ日時 2024-09-29 23:02:01
合計ジャッジ時間 4,749 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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;



using namespace std;

// https://ja.wikipedia.org/wiki/プリューファー列
vector<pair<int, int>> random_tree(int N) {
    vector<pair<int, int>> edges;

    vector<int> p(N - 2);
    for (auto&& x : p) {
        x = rng.range(1, N);
    }

    vector<int> d(N + 1, 1);
    for (auto&& x : p) {
        d[x]++;
    }

    priority_queue<int, vector<int>, greater<int>> pque;
    for (int i = 1; i <= N; i++) {
        if (d[i] == 1) pque.push(i);
    }

    for (auto&& i : p) {
        auto j = pque.top();
        pque.pop();

        edges.push_back({i, j});
        d[i]--;
        d[j]--;

        if (d[i] == 1) pque.push(i);
        if (d[j] == 1) pque.push(j);
    }

    int u = pque.top();
    pque.pop();
    int v = pque.top();
    pque.pop();
    assert(pque.empty());

    edges.push_back({u, v});

    for (auto&& pa : edges) {
        pa.first--;
        pa.second--;
    }

    return edges;
}

int main(int argc, char* argv[]) {
    const int seed = 7654345;
    rng.setSeed(seed);

    const int N = 200000;

    auto edges = random_tree(N);

    cout << N << endl;
    for (auto&& [u, v] : edges) {
        cout << min(u, v) + 1 << ' ' << max(u, v) + 1 << endl;
    }
}
0