読者です 読者をやめる 読者になる 読者になる

kmjp's blog

競技プログラミング参加記です

Codeforces #403 Div1 A. Andryusha and Colored Balloons

Codeforces

Dまではいつもより簡単目。
http://codeforces.com/contest/781/problem/A

問題

N頂点からなる木を成すグラフが与えられる。
このグラフの頂点を彩色したい。
3頂点(A,B,C)がA-B-Cと辺でつながっているとき、その3頂点は異なる色でなければならないとする。
必要な色数の最小値を求め、塗り分けの一例を示せ。

解法

根付き木とみなし、根から順にDFSで色を確定させていく。
その際、各頂点ではsetでその頂点自身および隣接点の色の集合を保持しよう。

DFSをしていくとき、各頂点では親頂点およびその隣接頂点で未使用の色のうち最小値を求めればよい。
その際、毎回setを全探索して最小値を求めるとO(N^2)かかってTLEしかねないので、前回探索した範囲を再探索しないようにしよう。

int N;
vector<int> E[201010];
set<int> S[201010];
int C[201010],P[201010];
int ma;
void dfs(int cur,int pre) {
	if(pre!=-1) {
		while(S[pre].count(P[pre])) P[pre]++;
		C[cur]=P[pre];
		S[pre].insert(C[cur]);
		S[cur].insert(C[pre]);
	}
	S[cur].insert(C[cur]);
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(0,-1);
	_P("%d\n",*max_element(C,C+N)+1);
	FOR(i,N) _P("%d ",C[i]+1);
	_P("\n");
}

まとめ

750ptでもいいかなと思った。

広告を非表示にする