結果

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

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>

namespace nachia {

struct RegularBipartiteGraph {
    int n;
    int k;
    std::vector<std::pair<int, int>> edges;
};

RegularBipartiteGraph BipartiteRegularizeEdgeColorEquivalent(
    int n1,
    int n2,
    std::vector<std::pair<int,int>> edges
){
    std::vector<int> ind1(n1);
    std::vector<int> ind2(n2);
    for(auto [u,v] : edges){ ind1[u]++; ind2[v]++; }
    int k = std::max(
        *std::max_element(ind1.begin(), ind1.end()),
        *std::max_element(ind2.begin(), ind2.end()));
    std::vector<int> map1(n1);
    std::vector<int> map2(n2);
    std::vector<int> indx1(std::max(n1, n2));
    std::vector<int> indx2(std::max(n1, n2));
    indx1[0] += ind1[0];
    for(int i=1; i<n1; i++){
        map1[i] = map1[i-1];
        if(indx1[map1[i]] + ind1[i] > k) map1[i]++;
        indx1[map1[i]] += ind1[i];
    }
    indx2[0] += ind2[0];
    for(int i=1; i<n2; i++){
        map2[i] = map2[i-1];
        if(indx2[map2[i]] + ind2[i] > k) map2[i]++;
        indx2[map2[i]] += ind2[i];
    }
    int n = std::max(map1.back() + 1, map2.back() + 1);
    RegularBipartiteGraph res = { n, k, std::vector<std::pair<int,int>>(n*k) };
    for(int i=0; i<int(edges.size()); i++){
        res.edges[i] = { map1[edges[i].first], map2[edges[i].second] };
    }
    int s1 = 0;
    int s2 = 0;
    for(int i=int(edges.size()); i<n*k; i++){
        while(indx1[s1] == k) s1++;
        while(indx2[s2] == k) s2++;
        res.edges[i] = { s1, s2 };
        indx1[s1]++; indx2[s2]++;
    }
    return res;
}

std::vector<int> RegularBipartiteEdgeColor(const RegularBipartiteGraph& g){
    int n = g.n * 2;
    std::vector<int> inci(n * g.k);
    int m = g.n * g.k;
    std::vector<int> xedge(m); {
        std::vector<int> head(n);
        for(int e=0; e<m; e++){
            auto [u,v] = g.edges[e];
            inci[g.k*(u*2+0) + head[u*2+0]++] = e;
            inci[g.k*(v*2+1) + head[v*2+1]++] = e;
            xedge[e] = (u*2+0) ^ (v*2+1);
        }
    }
    std::vector<int> flag_e(m);
    int nx_flag = 0;
    auto euler_splitting = [&](
        std::vector<int> pl,
        std::vector<int> pr
    ) -> std::vector<int> {
        nx_flag++;
        for(int sp=0; sp<n; sp++){
            int v = sp;
            while(true){
                if(pl[v] == pr[v]){
                    if(sp == v) break;
                    v ^= 1;
                    continue;
                }
                int e = inci[pl[v]++];
                int w = v;
                if(flag_e[e] != nx_flag){
                    flag_e[e] = nx_flag;
                    w = v ^ xedge[e];
                }
                if(w % 2 == 0) std::swap(inci[--pl[v]], inci[--pr[v]]);
                v = w;
            }
        }
        return pl;
    };
    auto swap_group = [&](
        const std::vector<int>& el,
        std::vector<int>& em,
        const std::vector<int>& er
    ) -> void {
        for(int i=0; i<n; i++){
            int len = std::min(em[i] - el[i], er[i] - em[i]);
            std::swap_ranges(
                inci.begin() + el[i],
                inci.begin() + (el[i] + len),
                inci.begin() + (er[i] - len));
            em[i] = er[i] + el[i] - em[i];
        }
    };
    auto take_matching = [&](
        int s, int d
    ) -> void {
        std::vector<int> pl(n);
        std::vector<int> pr(n);
        for(int i=0; i<n; i++) pl[i] = i * g.k + s;
        for(int i=0; i<n; i++) pr[i] = i * g.k + s + d;
        std::vector<int> pm = pr;
        int md = 1; while(md < n/2*d) md *= 2;
        int alpha = md / d;
        while(alpha % 2 == 0){ alpha /= 2; md /= 2; }
        for(int w=1; w<md; w*=2){
            if(alpha & w){
                auto plm = euler_splitting(pl, pm);
                int count_edges = 0;
                for(int i=0; i<n; i+=2) count_edges += pm[i] + pl[i] - plm[i] * 2;
                if(count_edges < 0) swap_group(pl, plm, pm);
                std::swap(pm, plm);
            } else {
                auto pmr = euler_splitting(pm, pr);
                int count_edges = 0;
                for(int i=0; i<n; i+=2) count_edges += pr[i] + pm[i] - pmr[i] * 2;
                if(count_edges < 0) swap_group(pm, pmr, pr);
                std::swap(pm, pmr);
            }
        }
    };
    auto part_color = [&](
        auto& rec,
        int s, int d
    ) -> void {
        if(d <= 1) return;
        int d2 = d;
        if(d2 % 2 == 1){
            if(s+d2 < g.k) d2++;
            else{ take_matching(s, d2); d2--; }
        }
        std::vector<int> pl(n);
        std::vector<int> pr(n);
        for(int i=0; i<n; i++) pl[i] = i * g.k + s;
        for(int i=0; i<n; i++) pr[i] = i * g.k + s + d2;
        euler_splitting(std::move(pl), std::move(pr));
        rec(rec, s+d2/2, d2/2);
        rec(rec, s, d2/2);
    };
    part_color(part_color, 0, g.k);
    std::vector<int> ans(m);
    for(int i=0; i<n; i+=2) for(int j=0; j<g.k; j++) ans[inci[i*g.k+j]] = j;
    return ans;
}

std::vector<int> BipartiteEdgeColor(
    int n1,
    int n2,
    std::vector<std::pair<int,int>> edges
){
    int m = edges.size();
    auto regularized = BipartiteRegularizeEdgeColorEquivalent(n1, n2, std::move(edges));
    auto ans = RegularBipartiteEdgeColor(regularized);
    ans.resize(m);
    return ans;
}

} // namespace nachia
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};
}

void testcase(){
    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);
        }
    }

    vector<int> deg(N);
    rep(i,N) deg[i] = edges[i].size();
    auto [Q, vcolor] = bin_packing(deg);

    vector<pair<int,int>> bedge;
    rep(i,N) rep(j,edges[i].size()){
        bedge.push_back({ vcolor[i], edges[i][j] });
        edges[i][j] = int(bedge.size()) - 1;
    }

    auto bcolor = nachia::BipartiteEdgeColor(Q, N-1, bedge);

    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;
}
0