結果

問題 No.2987 Colorful University of Tree
ユーザー 👑 hos.lyric
提出日時 2024-12-13 08:16:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 802 ms / 5,000 ms
コード長 9,510 bytes
コンパイル時間 2,339 ms
コンパイル使用メモリ 141,172 KB
実行使用メモリ 65,080 KB
最終ジャッジ日時 2024-12-13 08:17:14
合計ジャッジ時間 26,305 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 42
権限があれば一括ダウンロードができます

ソースコード

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

// no proof, please hack me
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i 
    >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
// !!!Modifies ns and edges!!!
// n: modified regular bipartite graph
// d := max degree = edge chromatic number
// iss[c]: edges of color c \in [0, d)
// colors[i]: color of edge i
struct BipartiteEdgeColoring {
  int ns[2];
  vector<pair<int, int>> edges;
  int n;
  int d;
  vector<int> colors;
  vector<vector<int>> iss;
  BipartiteEdgeColoring() {}
  BipartiteEdgeColoring(int n0, int n1) : ns{n0, n1}, edges() {}
  void ae(int u, int v) {
    assert(0 <= u); assert(u < ns[0]);
    assert(0 <= v); assert(v < ns[1]);
    edges.emplace_back(u, v);
  }
  void run() {
    const int m = edges.size();
    vector<int> deg[2];
    for (int s = 0; s < 2; ++s) deg[s].assign(ns[s], 0);
    for (const auto &edge : edges) {
      ++deg[0][edge.first];
      ++deg[1][edge.second];
    }
    d = 0;
    for (int s = 0; s < 2; ++s) for (int u = 0; u < ns[s]; ++u) if (d < deg[s][u]) d = deg[s][u];
    // Merge vertices of small degree.
    for (int s = 0; s < 2; ++s) {
      priority_queue<pair<int, int>, vector<pair<int, int>>, std::greater<pair<int, int>>> que;
      par.resize(ns[s]);
      for (int u = 0; u < ns[s]; ++u) que.emplace(deg[s][u], par[u] = u);
      for (; ; ) {
        if (!que.size()) break;
        const auto p0 = que.top(); que.pop();
        if (!que.size()) break;
        const auto p1 = que.top(); que.pop();
        if (p0.first + p1.first > d) break;
        par[p0.second] = p1.second;
        que.emplace(p0.first + p1.first, p1.second);
      }
      int nn = 0;
      vector<int> ids(ns[s], -1);
      for (int u = 0; u < ns[s]; ++u) if (par[u] == u) ids[u] = nn++;
      ns[s] = nn;
      if (s == 0) {
        for (auto &edge : edges) edge.first = ids[root(edge.first)];
      } else {
        for (auto &edge : edges) edge.second = ids[root(edge.second)];
      }
    }
    // Add edges to make the graph d-regular.
    n = max(ns[0], ns[1]);
    for (int s = 0; s < 2; ++s) deg[s].assign(n, 0);
    for (const auto &edge : edges) {
      ++deg[0][edge.first];
      ++deg[1][edge.second];
    }
    for (int u = 0, v = 0; ; ) {
      for (; u < n && deg[0][u] >= d; ++u) {}
      for (; v < n && deg[1][v] >= d; ++v) {}
      if (u == n && v == n) break;
      edges.emplace_back(u, v);
      ++deg[0][u];
      ++deg[1][v];
    }
    iss.clear();
    vector<int> is(n * d);
    for (int i = 0; i < n * d; ++i) is[i] = i;
    rec(is);
    // Remove added edges.
    colors.assign(m, -1);
    for (int k = 0; k < d; ++k) {
      iss[k].erase(std::lower_bound(iss[k].begin(), iss[k].end(), m), iss[k].end());
      for (const int i : iss[k]) colors[i] = k;
    }
  }
  vector<int> par;
  int root(int u) {
    return (par[u] == u) ? u : (par[u] = root(par[u]));
  }
  // is: k-regular
  void rec(vector<int> is) {
    if (!is.size()) return;
    const int k = is.size() / n;
    if (k == 1) {
      std::sort(is.begin(), is.end());
      iss.push_back(is);
    } else if (k % 2 != 0) {
      if (iss.size()) {
        is.insert(is.end(), iss.back().begin(), iss.back().end());
        iss.pop_back();
        rec(is);
      } else {
        // Add (2^e - k) bad matchings to find a perfect matching.
        const int e = (31 - __builtin_clz(k)) + 1;
        vector<int> ma(n);
        for (int u = 0; u < n; ++u) ma[u] = ~u;
        for (; ; ) {
          auto js = is;
          for (const int j : ma) for (int l = 0; l < (1 << e) - k; ++l) js.push_back(j);
          for (int f = e; --f >= 0; ) {
            const auto jss = euler(js);
            int numBads[2] = {};
            for (int s = 0; s < 2; ++s) for (const int i : jss[s]) if (i < 0) ++numBads[s];
            js = jss[(numBads[0] <= numBads[1]) ? 0 : 1];
          }
          ma.swap(js);
          bool good = true;
          for (const int j : ma) if (j < 0) {
            good = false;
            break;
          }
          if (good) break;
        }
        std::sort(ma.begin(), ma.end());
        iss.push_back(ma);
        std::sort(is.begin(), is.end());
        vector<int> iis;
        auto it = ma.begin();
        for (const int i : is) {
          for (; it != ma.end() && *it < i; ++it) {}
          if (!(it != ma.end() && *it == i)) iis.push_back(i);
        }
        rec(iis);
      }
    } else {
      const auto jss = euler(is);
      for (int s = 0; s < 2; ++s) rec(jss[s]);
    }
  }
  // Take Eulerian circuit and take edges alternately.
  vector<vector<int>> euler(const vector<int> &is) {
    const int k = is.size() / n;
    vector<int> pt(n + n);
    for (int u = 0; u < n + n; ++u) pt[u] = u * k;
    vector<pair<int, int>> xvs((n + n) * k);
    for (int x = 0; x < n * k; ++x) {
      const int i = is[x];
      int u, v;
      if (i >= 0) {
        u = edges[i].first;
        v = n + edges[i].second;
      } else {
        u = ~i;
        v = n + ~i;
      }
      xvs[pt[u]++] = std::make_pair(x, v);
      xvs[pt[v]++] = std::make_pair(x, u);
    }
    vector<int> used(n * k, 0);
    int y = 0;
    vector<vector<int>> jss(2, vector<int>(n * (k / 2)));
    vector<int> stack;
    for (int u0 = 0; u0 < n; ++u0) {
      for (stack.push_back(u0); stack.size(); ) {
        const int u = stack.back();
        if (pt[u] > u * k) {
          --pt[u];
          const int x = xvs[pt[u]].first;
          const int v = xvs[pt[u]].second;
          if (!used[x]) {
            used[x] = 1;
            jss[y & 1][y >> 1] = is[x];
            ++y;
            stack.push_back(v);
          }
        } else {
          stack.pop_back();
        }
      }
    }
    return jss;
  }
};
////////////////////////////////////////////////////////////////////////////////
vector<int> greedy(const vector<int> &deg, int m) {
  const int n = deg.size();
  priority_queue<pair<int, int>> que;
  for (int i = 0; i < m; ++i) que.emplace(m, i);
  vector<pair<int, int>> dus(n);
  for (int u = 0; u < n; ++u) dus[u] = make_pair(deg[u], u);
  sort(dus.begin(), dus.end(), greater<pair<int, int>>{});
  vector<int> ret(n, 0);
  for (const auto &du : dus) {
    const int c = que.top().first;
    const int i = que.top().second;
    que.pop();
    if (c < du.first) return {};
    que.emplace(c - du.first, i);
    ret[du.second] = i;
  }
  return ret;
}
int getM(const vector<int> &deg) {
  const int n = deg.size();
  Int m = 0;
  for (; !(2 * n - 2 <= m * m); ++m) {}
  for (int u = 0; u < n; ++u) chmax<Int>(m, deg[u]);
  // girigiri, but too few odd
  Int sum = 0;
  for (int u = 0; u < n; ++u) sum += deg[u] / 2;
  for (; !(sum <= m * (m/2)); ++m) {}
  return m;
}
namespace exper {
int N;
vector<int> deg;
Int counter;
void test() {
// cerr<<"[test] "<<deg<<endl;
  ++counter;
  const int m = getM(deg);
  const auto res = greedy(deg, m);
  if (!res.size()) {
    cerr << "FAIL " << deg << " " << m << endl;
    assert(false);
  }
}
void dfs(int u, int e, int d) {
  if (e > (N - u) * d) return;
  if (u == N) {
    test();
  } else {
    for (chmin(d, e); d >= 0; --d) {
      deg[u] = 1 + d;
      dfs(u + 1, e - d, d);
    }
  }
}
void run() {
  for (N = 2; ; ++N) {
    deg.resize(N);
    counter = 0;
    dfs(0, N - 2, N - 2);
    cerr << "PASSED N = " << N << ": counter = " << counter << endl;
  }
}
}  // exper
// DONE N = 83: counter = 18004327
int N;
vector<int> C;
vector<vector<int>> E;
int main() {
  // exper::run();
  
  for (int numCases; ~scanf("%d", &numCases); ) { for (int caseId = 1; caseId <= numCases; ++caseId) {
    scanf("%d", &N);
    C.resize(N);
    E.resize(N);
    for (int u = 0; u < N; ++u) {
      scanf("%d", &C[u]);
      E[u].resize(C[u]);
      for (int c = 0; c < C[u]; ++c) {
        scanf("%d", &E[u][c]);
        --E[u][c];
      }
    }
    
    const int M = getM(C);
    const auto res = greedy(C, M);
    
    /*
      side 0: endpoints of edge
      side 1: edge from same vertex color
    */
    BipartiteEdgeColoring bec(N - 1, M);
    for (int u = 0; u < N; ++u) {
      for (int c = 0; c < C[u]; ++c) {
        bec.ae(E[u][c], res[u]);
      }
    }
    bec.run();
    assert(bec.d <= M);
    
    printf("%d\n", M);
    int id = 0;
    for (int u = 0; u < N; ++u) {
      printf("%d", res[u] + 1);
      for (int c = 0; c < C[u]; ++c) {
        printf(" %d", bec.colors[id++] + 1);
      }
      puts("");
    }
  }
#ifndef LOCAL
  break;
#endif
  }
  return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0