Codeforces #1026 : Div2 E. Melody

これも割とすんなり解いてる。
https://codeforces.com/contest/2110/problem/E

問題

N個の音からなる音楽を奏でたい。
各音iは、ボリュームV[i]と高さP[i]からなる。
音をN個並べる際、連続する2音は、ボリュームと高さのいずれかが一致しなければならない。
また、連続する3音で、ボリュームまたは高さが一致してはならない。

条件を満たす音の並びを1つ構成せよ。
なお、ボリュームも高さも一致する2音は与えられない。

解法

ボリュームと高さに対応する点からなる二部グラフを考える。
N個の音に対応し、ボリュームと高さに対応する点をつなぐ辺を張ろう。
あとはこれに対しハミルトンパスを求めればよい。

int T,N;
template<int MV> class UndirectedEulerPath {
public:
	int NV;
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }

	
	void init(int NV){
		this->NV=NV;
		for(int i=0;i<NV;i++) E[i].clear();
		path.clear();
	}
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath(int root=-1) { // 開始地点を探し、条件を満たすか判定
		int fo=-1,odd=0,i,np=0;
		assert(NV);
		FOR(i,NV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		//閉路なら奇数を許容しないようにしておく
		if(odd!=0 && odd!=2) return false;
		if(root==-1) {
			if(odd) {
				root=fo;
			}
			else {
				FOR(i,NV) if(E[i].size()) root=i;
			}
		}
		else {
			if(odd==2&&E[root].size()%2==0) return false;
		}
		dfs(root);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}
};

UndirectedEulerPath<401000> uep;
int X[202020],Y[202020];
map<pair<int,int>,int> M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		vector<int> Xs,Ys;
		M.clear();
		FOR(i,N) {
			cin>>X[i]>>Y[i];
			Xs.push_back(X[i]);
			Ys.push_back(Y[i]);
		}
		sort(ALL(Xs));
		sort(ALL(Ys));
		Xs.erase(unique(ALL(Xs)),Xs.end());
		Ys.erase(unique(ALL(Ys)),Ys.end());
		uep.init(Xs.size()+Ys.size());
		FOR(i,N) {
			X[i]=lower_bound(ALL(Xs),X[i])-Xs.begin();
			Y[i]=lower_bound(ALL(Ys),Y[i])-Ys.begin()+Xs.size();
			M[{X[i],Y[i]}]=M[{Y[i],X[i]}]=i;
			uep.add_path(X[i],Y[i]);
		}
		if(uep.GetPath()) {
			cout<<"YES"<<endl;
			FOR(i,uep.path.size()-1) {
				cout<<M[{uep.path[i],uep.path[i+1]}]+1<<" ";
			}
			cout<<endl;
		}
		else {
			cout<<"NO"<<endl;
		}
		
		
	}
}

まとめ

コードが一見長く見えるけど、ライブラリと座標圧縮がほとんど。