【学习笔记】[COCI2018-2019#1] Teoretičar

首先，可以发现$C$等于所有点度数的最大值，我们能用到的颜色数目为$2^x\ge C$。

考虑分治，将边集划分为$E=E_1+E_2$，使得$E_1,E_2$中点度数的最大值都不超过$2^{x-1}$。这样，我们将$[1,2^{x-1}]$中的颜色分配给$E_1$，$[2^{x-1}+1,2^x]$中的颜色分配给$E_2$，就可以递归到子问题。显然当$C=1$时，可以将所有边染成同一个颜色。

显然，我们可以用欧拉回路解决这个问题。但是这个做法常数比较大。考虑 CF1499G Graph Coloring 的做法，维护若干个环和若干条端点互不相同的链（因为是二分图，所以环的长度一定是偶数），这可以用带权并查集维护。注意并查集的维护对象是每条边，合并两条边的时候限制等价于这两条边所属集合不同。

复杂度$O(m\log m)$。

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define inf 0x3f3f3f3f
using namespace std;
const int N=2e5+5;
const int M=5e5+5;
int L,R,m,U[M],V[M],du[N],st[N];
int fa[M],val[M],tag[M],res[M];
vector<int>v;
int find(int x){if(fa[x]==x)return x;int tmp=fa[x];fa[x]=find(fa[x]);val[x]^=val[tmp];return fa[x];
}
void upd(int x){find(x);if(!(val[x]^tag[fa[x]])){tag[fa[x]]^=1;}
}
void unionset(int x,int y){int u=find(x),v=find(y);if(u!=v){val[u]=val[x]^val[y]^1,fa[u]=v;}
}
void solve(vector<int>&v,int cur){if(v.size()==0)return;for(auto e:v){fa[e]=e,val[e]=0,tag[e]=0,st[U[e]]=st[V[e]]=0;}int f=0;for(auto e:v){int x=U[e],y=V[e];if(st[x]||st[y])f=1;if(!st[x]&&!st[y]){st[x]=st[y]=e;}else if(!st[x]){upd(st[y]);unionset(e,st[y]);st[x]=e,st[y]=0;}else if(!st[y]){upd(st[x]);unionset(e,st[x]);st[y]=e,st[x]=0;}else{upd(st[x]),upd(st[y]);unionset(e,st[x]),unionset(e,st[y]);st[x]=st[y]=0;}}if(f==0){for(auto e:v)res[e]=1;}else{vector<int>vl,vr;for(auto e:v){find(e);if(val[e]^tag[fa[e]]){vr.pb(e);}else{vl.pb(e);}}solve(vl,cur>>1),solve(vr,cur>>1);for(auto e:vr)res[e]+=cur>>1;}
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>L>>R>>m;for(int i=1;i<=m;i++){cin>>U[i]>>V[i],V[i]+=L;du[U[i]]++,du[V[i]]++,v.pb(i);}int dmax=0;for(int i=1;i<=L+R;i++)dmax=max(dmax,du[i]);int x=2;while(x<dmax)x<<=1;solve(v,x);cout<<x<<"\n";for(int i=1;i<=m;i++)cout<<res[i]<<"\n";
}