結果

問題 No.2987 Colorful University of Tree
ユーザー 👑 Nachia
提出日時 2024-12-02 00:47:49
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 330 ms / 5,000 ms
コード長 5,571 bytes
コンパイル時間 1,725 ms
コンパイル使用メモリ 133,044 KB
最終ジャッジ日時 2025-02-26 10:25:06
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
#include <unordered_map>
#include <cassert>
#include <cstdint>
#include <array>
class Xoshiro256pp{
public:
    using i64 = long long;
    using u64 = unsigned long long;
private:
    std::array<u64, 4> s;
    static inline uint64_t rotl(const uint64_t x, int k) noexcept {
        return (x << k) | (x >> (64 - k));
    }
    inline uint64_t gen(void) noexcept {
        const uint64_t result = rotl(s[0] + s[3], 23) + s[0];
        const uint64_t t = s[1] << 17;
        s[2] ^= s[0];
        s[3] ^= s[1];
        s[1] ^= s[2];
        s[0] ^= s[3];
        s[2] ^= t;
        s[3] = rotl(s[3], 45);
        return result;
    }
public:
    Xoshiro256pp(){
        s[0] = 0x8e1281ee837ab726;
        s[1] = 0xbe54f8d4f619af0d;
        s[2] = 0x0d989b2579a56e23;
        s[3] = 0x7b3c16005b6dddf9;
    }
    
    u64 rng64() { return gen(); }
    // generate x : l <= x <= r
    u64 random_unsigned(u64 l,u64 r){
        assert(l<=r);
        r-=l;
        auto res = rng64();
        if(res<=r) return res+l;
        u64 d = r+1;
        u64 max_valid = 0xffffffffffffffff/d*d;
        while(true){
            auto res = rng64();
            if(res<=max_valid) break;
        }
        return res%d+l;
    }
};
using namespace std;
#define rep(i,n) for(int i=0; i<int(n); i++)
pair<int, vector<int>> bin_packing(vector<int> weight){
    int N = weight.size();
    int N_original = N;
    int odd_count = 0;
    for(int a : weight) if(a % 2 == 1) odd_count += 1;
    int sum = N * 2 - 2;
    int Q = *max_element(weight.begin(), weight.end());;
    while(true){
        int req = sum;
        if(Q % 2 == 1) req += max(0, Q - odd_count);
        if(req <= (long long)Q * Q) break;
        Q += 1;
    }
    int P = (sum + Q - 1) / Q;
    if(P < Q) P += 1;
    while(sum < P*Q){
        weight.push_back(1);
        sum += 1;
        N += 1;
        odd_count += 1;
    }
    set<pair<int,int>> even_group, odd_group;
    rep(i,N) (weight[i] % 2 ? odd_group : even_group).insert({ -weight[i], i });
    even_group.insert({ 1, -100 });
    odd_group.insert({ 1, -100 });
    vector<int> ans(N, -1);
    auto set_ans = [&](int i, int c){
        if(i < 0) exit(1);
        (weight[i] % 2 ? odd_group : even_group).erase({ -weight[i], i });
        ans[i] = c;
        if(weight[i] % 2 == 1) odd_count -= 1;
    };
    auto extract_max_at = [&](set<pair<int,int>>& src, int x){
        pair<int,int> res = *src.lower_bound({ -x, -1 });
        res.first *= -1;
        return res;
    };
    auto extract_max = [&](int x){
        return max(extract_max_at(even_group, x), extract_max_at(odd_group, x));
    };
    
    rep(i,P){
        int to_pack = Q;
        if(Q % 2 == 1){
            if(odd_count == P - i){
                auto [w,v] = extract_max_at(odd_group, to_pack);
                set_ans(v, i);
                to_pack -= w;
            }
            while(to_pack > 0){
                auto [w,v] = (odd_count == P-i-1) ? extract_max_at(even_group, to_pack) : extract_max(to_pack);
                set_ans(v, i);
                to_pack -= w;
            }
        } else {
            while(to_pack > 0){
                auto [w,v] = extract_max(to_pack);
                set_ans(v, i);
                to_pack -= w;
            }
        }
    }
    ans.resize(N_original);
    return {Q,ans};
}
#include <random>
#include <chrono>
void testcase(){
    // input
    int N; cin >> N;
    vector<vector<int>> edges(N);
    rep(i,N){
        int c; cin >> c;
        rep(j,c){
            int e; cin >> e; e--;
            edges[i].push_back(e);
        }
    }
    // node color
    vector<int> deg(N);
    rep(i,N) deg[i] = edges[i].size();
    auto [Q, vcolor] = bin_packing(deg);
    // heuristic
    vector<int> bedge(N*2-2);
    vector<int> eVisCount(N-1, 0);
    rep(i,N) rep(j,edges[i].size()){
        int e = edges[i][j];
        bedge[e*2 + eVisCount[e]] = vcolor[i];
        edges[i][j] = e*2 + eVisCount[e];
        eVisCount[e]++;
    }
    
    Xoshiro256pp rng;
    vector<int> vacant(Q, 0);
    vector<int> bcolor(N*2-2);
    rep(e,N*2-2) bcolor[e] = vacant[bedge[e]]++;
    vector<vector<int>> maps(Q);
    rep(q,Q) maps[q].resize(vacant[q]+1);
    rep(e,N*2-2) maps[bedge[e]][bcolor[e]] = e;
    vector<int> conflict;
    rep(i,N-1) if(bcolor[i*2] == bcolor[i*2+1]) conflict.push_back(i);
    while(conflict.size()){
        int ex = conflict.back(); conflict.pop_back();
        int e0 = ex * 2 + 0;
        int e1 = ex * 2 + 1;
        if(bcolor[e0] != bcolor[e1]) continue;
        if(vacant[bedge[e0]] != Q){
            swap(vacant[bedge[e0]], bcolor[e0]);
            continue;
        }
        if(vacant[bedge[e1]] != Q){
            swap(vacant[bedge[e1]], bcolor[e1]);
            continue;
        }
        int f = (int)rng.random_unsigned(0, 2*(Q-1) - 1);
        if(f >= Q-1){ swap(e0, e1); f -= Q-1; }
        if(f >= bcolor[e0]) f++;
        int vcol = bedge[e0];
        int e0x = maps[vcol][f];
        swap(bcolor[e0x], bcolor[e0]);
        swap(maps[vcol][f], maps[vcol][bcolor[e0]]);
        if(bcolor[e0x] == bcolor[e0x^1]){
            conflict.push_back(e0x / 2);
        }
    }
    // output
    cout << Q << '\n';
    rep(i,N){
        cout << (vcolor[i] + 1);
        for(auto e : edges[i]) cout << ' ' << (bcolor[e] + 1);
        cout << '\n';
    }
}
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int T; cin >> T;
    rep(ti,T) testcase();
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0