Codeforces #801 : Div2 E. Ambiguous Dominoes

本番の難易度の割にupsolve数多い？
https://codeforces.com/contest/1695/problem/E

問題

N個のドミノが与えられる。それぞれ、2マス分のサイズに2つの整数が書かれている。
これらのドミノを敷き詰め、長方形状に並べることを考える。
全く同じ配置となるドミノが1個もないような
同じ整数の並びとなるドミノの敷き方が2通り以上あるような敷き方はあるか。
あるなら一例を示せ。

解法

整数値に対応する頂点を持つ無向グラフを考える。
ドミノに対応する2点間に辺を張ろう。

このグラフでDFS訪問順で(2k+1)要素の頂点を並べることができたとき、そこからk個のドミノを使う2パターンの置き方が生成できる。

int N;
multiset<int> E[602020];
vector<vector<pair<int,int>>> C;
vector<vector<pair<int,int>>> cand;

pair<int,int> dfs(int cur,pair<int,int> par) {
	pair<int,int> oth={0,0};
	while(E[cur].size()) {
		int e=*E[cur].begin();
		E[cur].erase(E[cur].find(e));
		E[e].erase(E[e].find(cur));
		auto p=dfs(e,{cur,e});
		if(p.first) {
			if(oth.first) {
				cand.push_back({p,oth});
				oth={0,0};
			}
			else {
				oth=p;
			}
		}
	}
	if(oth.first) {
		if(par.first) {
			cand.push_back({par,oth});
			return {0,0};
		}
		else {
			return oth;
		}
	}
	else return par;
		
	
}

vector<pair<int,int>> ret;
vector<string> P1;
vector<string> P2;



void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>x>>y;
		E[x].insert(y);
		E[y].insert(x);
	}
	
	for(i=1;i<=2*N;i++) if(E[i].size()) {
		cand.clear();
		auto p=dfs(i,{0,0});
		if(cand.empty()) {
			cout<<-1<<endl;
			return;
		}
		if(p.first) {
			cand.back().push_back(p);
		}
		FORR(c,cand) C.push_back(c);
	}
	
	FORR(c,C) {
		if(c.size()==2) {
			auto p1=c[0];
			auto p2=c[1];
			if(p1.first==p2.second) swap(p2.first,p2.second);
			if(p1.second==p2.second) swap(p2.first,p2.second),swap(p1.first,p1.second);
			if(p1.second==p2.first) swap(p1.first,p1.second);
			ret.push_back({p1.first,p1.second});
			ret.push_back({p2.second,p2.first});
			P1.push_back("LR");
			P1.push_back("LR");
			P2.push_back("UU");
			P2.push_back("DD");
		}
		else {
			int add=0;
			sort(ALL(c));
			do {
				auto p1=c[0];
				auto p2=c[1];
				auto p3=c[2];
				FOR(x,8) {
					if((x&1)==1) swap(p1.first,p1.second);
					if(x==2||x==6) swap(p2.first,p2.second);
					if(x==4) swap(p3.first,p3.second);
					if(p1.first==p2.first&&p1.first==p3.first) {
						ret.push_back({p1.first,p1.second});
						ret.push_back({p2.second,p2.first});
						ret.push_back({p3.first,p3.second});
					}
					else if(p1.second==p2.first&&p2.second==p3.first) {
						ret.push_back({p1.first,p1.second});
						ret.push_back({p2.first,p2.second});
						ret.push_back({p3.first,p3.second});
					}
					else {
						continue;
					}
					P1.push_back("LR");
					P1.push_back("UU");
					P1.push_back("DD");
					P2.push_back("UU");
					P2.push_back("DD");
					P2.push_back("LR");
					add++;
					break;
				}
				if(add) break;
			} while(next_permutation(ALL(c)));
			
		}
	}
	cout<<N<<" "<<2<<endl;
	FORR2(a,b,ret) cout<<a<<" "<<b<<endl;
	FORR(s,P1) cout<<s<<endl;
	FORR(s,P2) cout<<s<<endl;
	
	
}

まとめ

コード量結構多いんだけどな。