Codeforces #345 Div1. C. Table Compression

B相当位の難易度に見える。
http://codeforces.com/contest/650/problem/C

問題

N*Mの整数行列Aが与えられる。
この行列の要素を以下の条件を満たす範囲で書き換えたい。

• 各要素は1以上の整数である。
• 元のAにおいて、同じ行または同じ列にある2要素について、大小関係は圧縮後も変化しない。

書き換えた後のAの最大値が最小となるものを求めよ。

解法

Aのうち小さい順に1から割り当てていくのが基本方針である。

同じ行・列において同じ要素は、書き換え後も同じ値にしたい。
そこで、まず元のAにおいて同じ行・列の同じ要素同士をUnion-Findで連結しよう。

その後、各連結成分をその要素の昇順にソートする。
そして各連結成分毎に1から順に要素を割り当てよう。
その際、連結成分中の各要素について、同じ行または列に登場する(書き換え後の)値の最大値より1大きな値を順次割り当てていこう。

行または列の(書き換え後の)最大値を管理しておくと、この処理は高速に行える。

int H,W;
vector<vector<int>> A,R;
vector<int> C[1010101];
int MX[1010101];
int MY[1010101];

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<1100000> uf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	A.resize(H);
	R.resize(H);
	FOR(y,H) {
		A[y].resize(W);
		R[y].resize(W);
		FOR(x,W) cin>>A[y][x];
	}
	
	FOR(y,H) {
		vector<pair<int,int>> T;
		FOR(x,W) T.push_back({A[y][x],x});
		sort(ALL(T));
		FOR(i,W-1) if(T[i].first==T[i+1].first) uf(y*W+T[i].second,y*W+T[i+1].second);
	}
	FOR(x,W) {
		vector<pair<int,int>> T;
		FOR(y,H) T.push_back({A[y][x],y});
		sort(ALL(T));
		FOR(i,H-1) if(T[i].first==T[i+1].first) uf(T[i].second*W+x,T[i+1].second*W+x);
	}
	
	vector<pair<int,int>> V;
	FOR(y,H) FOR(x,W) {
		if(uf[y*W+x]==y*W+x) V.push_back({A[y][x],y*W+x});
		C[uf[y*W+x]].push_back(y*W+x);
	}
	sort(ALL(V));
	FORR(r,V) {
		y=r.second/W;
		x=r.second%W;
		R[y][x]=1;
		FORR(r2,C[r.second]) R[y][x]=max(R[y][x],max(MY[r2/W]+1,MX[r2%W]+1));
		FORR(r2,C[r.second]) {
			R[r2/W][r2%W]=R[y][x];
			MY[r2/W]=max(MY[r2/W],R[y][x]);
			MX[r2%W]=max(MX[r2%W],R[y][x]);
		}
	}
	FOR(y,H) FOR(x,W) _P("%d%s",R[y][x],(x==W-1)?"\n":" ");
}

まとめ

最初大小関係の維持は隣接要素同士だけかと思って勘違い。
とはいえ幸い余り迷わなかった。