結果

問題 No.8071 玉虫色着色
ユーザー opt
提出日時 2020-07-18 03:10:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 24 ms / 2,000 ms
コード長 6,862 bytes
コンパイル時間 3,420 ms
コンパイル使用メモリ 236,288 KB
最終ジャッジ日時 2025-01-11 23:54:25
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

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 T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
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() {
  int l, r, m; cin >> l >> r >> m;
  vector<pair<int, int>> E(m);
  cin >> E;

  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])));

  Edge_Coloring sol;
  deg = {V(l), V(r)};
  VVV vtx = {VV(l), VV(r)};
  rep(i, l) vtx[0][i].push_back(i);
  rep(i, r) vtx[1][i].push_back(i);

  rep(i, m) {
    auto [a, b] = E[i];
    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];
  }

  V res;
  int k = sol.run(res);
  cout << k << '\n';
  cout << res;
  return 0;
}
0