結果
問題 |
No.2987 Colorful University of Tree
|
ユーザー |
|
提出日時 | 2025-05-24 16:07:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 474 ms / 5,000 ms |
コード長 | 4,709 bytes |
コンパイル時間 | 2,720 ms |
コンパイル使用メモリ | 217,964 KB |
実行使用メモリ | 58,084 KB |
最終ジャッジ日時 | 2025-05-24 16:08:21 |
合計ジャッジ時間 | 20,420 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 42 |
ソースコード
#include <bits/stdc++.h> #define pb emplace_back #define fst first #define scd second #define mkp make_pair #define mems(a, x) memset((a), (x), sizeof(a)) using namespace std; typedef long long ll; typedef double db; typedef unsigned long long ull; typedef long double ldb; typedef pair<int, int> pii; namespace IO { const int maxn = 1 << 20; char ibuf[maxn], *iS, *iT, obuf[maxn], *oS = obuf; inline char gc() { return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, maxn, stdin), (iS == iT ? EOF : *iS++) : *iS++); } template<typename T = int> inline T read() { char c = gc(); T x = 0; bool f = 0; while (c < '0' || c > '9') { f |= (c == '-'); c = gc(); } while (c >= '0' && c <= '9') { x = (x << 1) + (x << 3) + (c ^ 48); c = gc(); } return f ? ~(x - 1) : x; } inline int reads(char *s) { char c = gc(); int len = 0; while (isspace(c)) { c = gc(); } while (!isspace(c)) { s[len++] = c; c = gc(); } return len; } inline void flush() { fwrite(obuf, 1, oS - obuf, stdout); oS = obuf; } struct Flusher { ~Flusher() { flush(); } } AutoFlush; inline void pc(char ch) { if (oS == obuf + maxn) { flush(); } *oS++ = ch; } template<typename T> inline void write(T x) { static char stk[64], *tp = stk; if (x < 0) { x = ~(x - 1); pc('-'); } do { *tp++ = x % 10; x /= 10; } while (x); while (tp != stk) { pc((*--tp) | 48); } } template<typename T> inline void writesp(T x) { write(x); pc(' '); } template<typename T> inline void writeln(T x) { write(x); pc('\n'); } } using IO::read; using IO::reads; using IO::write; using IO::pc; using IO::writesp; using IO::writeln; const int maxn = 200100; int n, ps[maxn], ord[maxn]; pair<pii, pii> e[maxn]; vector<int> G[maxn], T[maxn], vc[maxn]; int a[maxn], b[maxn], tot, c[maxn], g[maxn]; pii h[maxn]; inline bool check(int x) { priority_queue< pii, vector<pii>, greater<pii> > pq; for (int i = 1; i <= x; ++i) { pq.emplace(0, i); } for (int _ = 1; _ <= n; ++_) { int u = ord[_]; pii p = pq.top(); pq.pop(); if ((int)G[u].size() + p.fst > x) { return 0; } a[u] = p.scd; pq.emplace((int)G[u].size() + p.fst, p.scd); } return 1; } void solve() { n = read(); for (int i = 1; i <= n; ++i) { vector<int>().swap(G[i]); vector<int>().swap(vc[i]); } int l = ceil(sqrt(n * 2 - 2)); int r = min((int)sqrt(n * 4 - 4) + 2, n); for (int i = 1; i < n; ++i) { e[i] = mkp(mkp(0, 0), mkp(0, 0)); } for (int i = 1, k, x; i <= n; ++i) { k = read(); l = max(l, k); while (k--) { x = read(); G[i].pb(x); if (!e[x].fst.fst) { e[x].fst = mkp(i, (int)G[i].size() - 1); } else { e[x].scd = mkp(i, (int)G[i].size() - 1); } } ord[i] = i; } sort(ord + 1, ord + n + 1, [&](const int &x, const int &y) { return G[x].size() > G[y].size(); }); int ans = l; while (l <= r) { int mid = (l + r) >> 1; if (check(mid)) { ans = mid; r = mid - 1; } else { l = mid + 1; } } writeln(ans); check(ans); for (int i = 1; i <= n; ++i) { vc[a[i]].pb(i); } for (int i = 1; i <= n; ++i) { vector<int>(G[i].size()).swap(T[i]); } set<pii> S; for (int i = 1; i <= ans; ++i) { S.emplace(0, i); } for (int i = 1; i <= ans; ++i) { tot = 0; for (int j = 0; j < (int)vc[i].size(); ++j) { int u = vc[i][j]; for (int l = 0; l < (int)G[u].size(); ++l) { int k = G[u][l]; pii p = (e[k].fst.fst == u) ? e[k].scd : e[k].fst; h[++tot] = mkp(u, l); b[tot] = T[p.fst][p.scd]; if (b[tot]) { S.erase(mkp(g[b[tot]], b[tot])); ++g[b[tot]]; S.emplace(g[b[tot]], b[tot]); } } } auto it = S.begin(); bool fl = 1; for (int j = 1; j <= tot; ++j) { c[j] = (it++)->scd; fl &= (c[j] == b[j]); } if (fl) { int t = c[1]; for (int j = 1; j < tot; ++j) { c[j] = c[j + 1]; } c[tot] = t; } else { int tt = 0; for (int j = 1; j <= tot; ++j) { if (c[j] == b[j]) { ps[++tt] = j; } } for (int j = 1; j < tt; j += 2) { swap(c[ps[j]], c[ps[j + 1]]); } if (tt & 1) { int k = ps[tt]; for (int j = 1; j <= tot; ++j) { if (j == k) { continue; } if (c[j] != b[k] && c[k] != b[j]) { swap(c[j], c[k]); break; } } } } for (int j = 1; j <= tot; ++j) { T[h[j].fst][h[j].scd] = c[j]; if (b[j]) { S.erase(mkp(g[b[j]], b[j])); --g[b[j]]; S.emplace(g[b[j]], b[j]); } } } for (int i = 1; i <= n; ++i) { writesp(a[i]); for (int j = 0; j < (int)T[i].size(); ++j) { write(T[i][j]); pc(" \n"[j == (int)T[i].size() - 1]); } } } int main() { int T = read(); while (T--) { solve(); } return 0; }