キーエンス プログラミング コンテスト 2020 : E - Bichromization

これ意外にすんなり解けたのが助かった。
https://atcoder.jp/contests/keyence2020/tasks/keyence2020_e

問題

連結有向グラフが与えられる。また各点には正整数値が設定されている。
各点を白黒に塗り分け、かつ各辺の長さを設定し、「各頂点の設定値は、最寄の他色の頂点への距離」となるようにせよ。

解法

白黒交互に現れる木を構築しよう。残った辺は適当に大きな長さにしておけばよい。
木は以下のように構築する。
まず、自身の頂点の設定値が小さい順に処理することを考える。

• 隣接点に、自分の設定値以下の頂点があるなら、そことの間に自身の設定と同じ値の辺の長さを設定し、その頂点を確定済みとマークする。
• 隣接点をたどっても確定済みとマークできないなら解なし。

実際には、極小値が等しい隣接２頂点から初めて、隣接する点を徐々に確定させていくという動きとなる。

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<500000> uf;


int N,M;
ll D[202020];
pair<int,int> P[202020];
vector<pair<int,int>> E[101010];
int ret[202020],fix[101010];
string S;

void dfs(int cur,int pre,int i) {
	if(i) S[cur]='B';
	else S[cur]='W';
	FORR(e,E[cur]) if(e.first!=pre && ret[e.second]<1<<30) dfs(e.first,cur,i^1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>D[i];
		P[i]={D[i],i};
	}
	FOR(i,M) {
		cin>>x>>y;
		E[x-1].push_back({y-1,i});
		E[y-1].push_back({x-1,i});
		ret[i]=1<<30;
	}
	sort(P,P+N);
	FOR(i,N) {
		x=P[i].second;
		FORR(e,E[x]) if(uf[e.first]!=uf[x] && (D[e.first]==D[x] || (D[e.first]<D[x]&&fix[e.first]))) {
			ret[e.second]=D[x];
			if(D[e.first]==D[x]) fix[e.first]=1;
			fix[x]=1;
			uf(x,e.first);
		}
	}
	
	int num=0;
	FOR(i,N) if(uf[i]==i) num++;
	if(num>1) return _P("-1\n");
	
	S.resize(N);
	dfs(0,0,0);
	
	cout<<S<<endl;
	FOR(i,M) {
		if(ret[i]==1<<30) ret[i]=1000000000;
		cout<<ret[i]<<endl;
	}
}

まとめ

まぁまぁの考察で解けて良かったね。