結果

問題 No.2987 Colorful University of Tree
コンテスト
ユーザー raincity
提出日時 2025-05-24 16:51:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 627 ms / 5,000 ms
コード長 2,835 bytes
コンパイル時間 2,213 ms
コンパイル使用メモリ 205,952 KB
実行使用メモリ 44,696 KB
最終ジャッジ日時 2025-05-24 16:52:11
合計ジャッジ時間 21,900 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#ifdef LOCAL
#define err(...) (cout.flush(), fprintf(stderr, __VA_ARGS__))
#else
#define err(...) 42
#endif

#define all(x) begin(x), end(x)
#define len(x) int((x).size())

constexpr int N = 4e5 + 10;

int n, d[N];

int ord[N], ver_col[N];

bool AnsLe(int mid) {
    priority_queue<pair<int, int>> q;
    for (int i = 1; i <= mid; ++i)
        q.push({mid, i});
    for (int i = 1; i <= n; ++i) {
        auto [rest, id] = q.top();
        if (rest < d[ord[i]])
            return false;
        ver_col[ord[i]] = id;
        q.pop();
        q.push({rest - d[ord[i]], id});
    }
    return true;
}

int edges_col[N];
vector<int> large_adj[N], small_adj[N];

void Proc() {
    cin >> n;

    static int a[N], b[N];
    memset(a + 1, 0, (n - 1) * sizeof a[0]);
    for (int i = 1; i <= n; ++i) {
        cin >> d[i];
        large_adj[i].resize(d[i]);
        for (int &x : large_adj[i]) {
            cin >> x;
            if (a[x] == 0) {
                a[x] = i;
                x *= 2;
            } else {
                b[x] = i;
                x = 2 * x + 1;
            }
        }
    }

    iota(ord + 1, ord + n + 1, 1);
    sort(ord + 1, ord + n + 1, [&](int x, int y) {
        return d[x] > d[y];
    });

    int l = 0, r = 2 * (n - 1);
    while (l < r) {
        int mid = (l + r) >> 1;
        if (AnsLe(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << "\n";

    AnsLe(l);
    for (int i = 1; i <= l; ++i)
        small_adj[i].clear();
    for (int i = 1; i < n; ++i) {
        small_adj[ver_col[a[i]]].push_back(2 * i);
        small_adj[ver_col[b[i]]].push_back(2 * i + 1);
    }

    memset(edges_col + 2, 0, 2 * (n - 1) * sizeof edges_col[0]);
    for (int u = 1; u <= l; ++u) {
        int p1 = 1, p2 = 2, todo = 0;
        for (int e : small_adj[u]) {
            if (edges_col[e ^ 1] != p1) {
                edges_col[e] = p1;
                p1 = p2++;
            } else if (p2 <= l) {
                edges_col[e] = p2++;
            } else {
                todo = e;
            }
        }
        if (todo == 0)
            continue;

        bool found = false;
        for (int e : small_adj[u]) {
            if (edges_col[e ^ 1] != p1) {
                found = true;
                edges_col[todo] = edges_col[e];
                edges_col[e] = p1;
                break;
            }
        }
        assert(found);
    }

    for (int i = 1; i <= n; ++i) {
        cout << ver_col[i] << " ";
        for (int j : large_adj[i])
            cout << edges_col[j] << " ";
        cout << "\n";
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin.exceptions(ios::failbit);

    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i)
        Proc();
}
0