結果
問題 | No.8071 玉虫色着色 |
ユーザー |
|
提出日時 | 2020-07-18 08:25:44 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 35 ms / 2,000 ms |
コード長 | 6,848 bytes |
コンパイル時間 | 3,620 ms |
コンパイル使用メモリ | 243,248 KB |
最終ジャッジ日時 | 2025-01-12 00:08:56 |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
#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