結果

問題 No.3071 玉虫色着色
ユーザー 37zigen37zigen
提出日時 2020-07-18 08:25:44
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 6,848 bytes
コンパイル時間 4,284 ms
コンパイル使用メモリ 249,840 KB
実行使用メモリ 11,756 KB
最終ジャッジ日時 2023-09-11 08:04:07
合計ジャッジ時間 11,221 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 18 ms
11,404 KB
testcase_01 AC 9 ms
10,720 KB
testcase_02 AC 8 ms
10,544 KB
testcase_03 AC 11 ms
11,080 KB
testcase_04 AC 8 ms
10,588 KB
testcase_05 AC 8 ms
10,780 KB
testcase_06 AC 7 ms
10,588 KB
testcase_07 AC 21 ms
11,560 KB
testcase_08 AC 21 ms
11,756 KB
testcase_09 AC 20 ms
11,576 KB
testcase_10 AC 21 ms
11,612 KB
testcase_11 AC 21 ms
11,620 KB
testcase_12 AC 4 ms
9,896 KB
testcase_13 AC 5 ms
9,944 KB
testcase_14 AC 4 ms
9,960 KB
evil_large1.txt AC 313 ms
26,024 KB
evil_large2.txt AC 279 ms
27,764 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll = long long;
using V = vector<int>;
using VV = vector<V>;
using VVV = vector<VV>;
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define all(a) (a).begin(), (a).end()
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
template<typename T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
template<typename T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<typename T1, typename T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<typename T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << '\n'; return os; }


// Credit: Benq
typedef array<int,2> P;
typedef array<int,3> T;
template<int N,bool directed>struct Eulerian_Trail{
  vector<P> g[N]; vector<P>::iterator it[N];
  bool exist[N]; vector<int> vs; vector<bool> used;
  Eulerian_Trail(){rep2(i,0,N)exist[i]=0;}
  vector<int> res;
  void clear(){
    for(auto& v:vs)g[v].clear(),exist[v]=0;
    vs.clear(); used.clear(); res.clear();
  }
  void dfs(int v){
    vector<T> ret; stack<T> s; s.push({v,-1,-1});
    while(!s.empty()){
      int x=(s.top())[0];
      auto& cur=it[x],ed=g[x].end();
      while(cur!=ed and used[(*cur)[1]])cur++;
      if(cur==ed){ret.push_back(s.top()); s.pop();}
      else{s.push({(*cur)[0],x,(*cur)[1]}); used[(*cur)[1]]=1;}
    }
    rep2(i,0,ret.size()-1)res.push_back(ret[i][2]);
  }
  vector<int> run(vector<P> es){
    rep2(i,0,es.size()){
      auto [u,v]=es[i];
      used.push_back(0);
      if(!exist[u]){
        exist[u]=1; vs.push_back(u);
      }
      if(!exist[v]){
        exist[v]=1; vs.push_back(v);
      }
      g[u].push_back({v,i});
      g[v].push_back({u,i});
    }
    for(auto& v:vs)it[v]=g[v].begin();
    for(auto& v:vs)for(auto& e:g[v])if(!used[e[1]])dfs(e[0]);
    return res;
  }
};

struct Edge_Coloring{
  int n; vector<P> _es,es; Eulerian_Trail<201010,0> euler;
  Edge_Coloring(){}
  void add_edge(int u,int v){_es.push_back({u,v});}
  array<vector<int>,2> divide(vector<P> tmp){ //divide eulerian trail
    euler.clear(); auto p=euler.run(tmp); array<vector<int>,2> res;
    rep2(i,0,p.size())res[i&1].push_back(p[i]);
    return res;
  }
  vector<int> find(vector<int> ids){ //find perfect matching
    int k=(int)ids.size()/n; assert(n*k==(int)ids.size());
    int t=0; while((1<<t)<n*k)t++;
    int x=(1<<t)/k,y=(1<<t)%k;
    vector<int> ori(ids.size(),x),dum(n,y);
    while(t--){
      vector<P> tmp; vector<int> add; int cnt=0;
      rep2(i,0,ids.size()){
        if(ori[i]&1){
          tmp.push_back({es[ids[i]][0],es[ids[i]][1]});
          add.push_back(i); cnt++;
        } ori[i]>>=1;
      }
      rep2(i,0,n){
        if(dum[i]&1){
          tmp.push_back({i,n+i});
          add.push_back(i);
        } dum[i]>>=1;
      }
      array<vector<int>,2> w=divide(tmp); int dum_cnt[2]={};
      rep2(i,0,2)for(int x:w[i])if(x>=cnt)dum_cnt[i]++;
      for(int i:w[dum_cnt[0]>dum_cnt[1]]){
        if(i<cnt)ori[add[i]]++; else dum[add[i]]++;
      }
    }
    vector<int> res; rep2(i,0,ids.size())if(ori[i])res.push_back(ids[i]);
    assert((int)res.size()==n);
    return res;
  }
  vector<int> used;
  vector<vector<int>> colorize(vector<int> ids){ //must be regular bipartite graph
    int k=(int)ids.size()/n; assert(n*k==(int)ids.size());
    if(k==0)return {};
    if(k==1)return {ids};
    vector<vector<int>> res;
    if(k&1){
      auto add=find(ids);
      for(int x:add)used[x]=1;
      vector<int> rem;
      for(int x:ids)if(!used[x])rem.push_back(x);
      for(int x:add)used[x]=0;
      res=colorize(rem); res.push_back(add);
    }
    else{
      vector<P> tmp; for(int i:ids)tmp.push_back({es[i][0],es[i][1]});
      array<vector<int>,2> p=divide(tmp);
      rep2(i,0,2)for(auto& x:p[i])x=ids[x];
      res=colorize(p[0]);
      int cur=k>>1;
      while(__builtin_popcount(cur)!=1){
        auto add=res.back(); res.pop_back();
        p[1].insert(p[1].end(),all(add)); cur++;
      }
      auto add=colorize(p[1]);
      res.insert(res.end(),all(add));
    } return res;
  }
  int run(vector<int>& res){
    //normalize
    int LR[2]={}; for(auto e:_es)rep2(j,0,2)chmax(LR[j],e[j]+1);
    vector<int> deg[2],kind[2],sz[2];
    rep2(i,0,2)deg[i].resize(LR[i]),kind[i].resize(LR[i]);
    for(auto e:_es)rep2(j,0,2)deg[j][e[j]]++;
    int k=0; rep2(i,0,2)rep2(j,0,LR[i])chmax(k,deg[i][j]);
    rep2(j,0,2){
      for(int i=0;i<LR[j];){
        int add=0;
        while(i<LR[j] and deg[j][i]+add<=k){
          kind[j][i]=(int)sz[j].size();
          add+=deg[j][i++];
        } sz[j].push_back(add);
      }
    }
    rep2(i,0,2)while(sz[i].size()<sz[i^1].size())sz[i].push_back(0);
    n=(int)sz[0].size();
    for(auto e:_es)es.push_back({kind[0][e[0]],n+kind[1][e[1]]});
    int nxt=0;
    rep2(i,0,n)while(sz[0][i]<k){
      while(sz[1][nxt]==k)nxt++;
      es.push_back({i,n+nxt});
      sz[0][i]++; sz[1][nxt]++;
    }
    res.resize(_es.size()); used.resize(n*k,0);
    vector<int> tmp(n*k); iota(all(tmp),0);
    auto ret=colorize(tmp);
    rep2(i,0,ret.size())for(int idx:ret[i]){
      if(idx<(int)_es.size())res[idx]=i;
    }
    return k;
  }
};


int main() {
  // input
  int l, r, m; cin >> l >> r >> m;
  vector<pair<int, int>> E(m);
  cin >> E;

  // count degrees and find the minimum
  VV deg = {V(l), V(r)};
  for (auto [a, b] : E) { ++deg[0][a], ++deg[1][b]; }
  int D = min(*min_element(all(deg[0])), *min_element(all(deg[1])));

  // reset degree
  deg = {V(l), V(r)};

  // copied vertex set
  VVV vtx = {VV(l), VV(r)};
  rep(i, l) vtx[0][i].push_back(i);
  rep(i, r) vtx[1][i].push_back(i);

  // solution
  Edge_Coloring sol;

  // construct a graph with copied vertexes
  for (auto [a, b] : E) {
    int x = vtx[0][a].back();
    int y = vtx[1][b].back();
    if (deg[0][x] == D) {
      vtx[0][a].push_back(deg[0].size());
      x = vtx[0][a].back();
      deg[0].push_back(0);
    }
    if (deg[1][y] == D) {
      vtx[1][b].push_back(deg[1].size());
      y = vtx[1][b].back();
      deg[1].push_back(0);
    }
    sol.add_edge(x, y);
    ++deg[0][x];
    ++deg[1][y];
  }

  // find edge coloring
  V res;
  sol.run(res);

  // verify //
  vector<set<int>> S0(l), S1(r);
  rep(i, m) {
    auto [a, b] = E[i]; 
    S0[a].insert(res[i]);
    S1[b].insert(res[i]);
  }
  rep(i, l) assert(S0[i].size() == D);
  rep(i, r) assert(S1[i].size() == D);
  ////////////

  // output
  cout << D << '\n';
  cout << res;
  return 0;
}

// 5 3 10
// 0 0
// 0 1
// 1 0
// 1 2
// 2 1
// 2 2
// 3 1
// 3 2
// 4 1
// 4 2
0