結果
問題 |
No.2987 Colorful University of Tree
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
#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(); }