Codeforces #351 Div1 B. Bear and Two Paths

そこそこ手こずってしまった。
http://codeforces.com/contest/674/problem/B

問題

N頂点K辺の無向グラフを作りたい。
異なる４頂点A,B,C,Dが与えられるとき、以下の条件を満たすグラフが作れ。

• AとB、CとDをそれぞれ直接つなぐ辺はない。
• AからBに全頂点を１回ずつたどって到達するパスがある。
• CからDに全頂点を１回ずつたどって到達するパスがある。

解法

A,B,C,D以外の頂点が存在するとき、それらを順にX..Zとする。
A-C-Xを三角形状に結び、B-D-Zを三角形状に結び、X..Zを順に結べば、A-C-X...Z-D-B、C-A-X...Z-B-Dとたどれるのでいずれも条件を満たす。
その際、N＞4であることとK≧N+1である必要がある。

int N,K;
int A,B,C,D;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	cin>>A>>B>>C>>D;
	vector<int> V;
	for(i=1;i<=N;i++) {
		if(i==A) continue;
		if(i==B) continue;
		if(i==C) continue;
		if(i==D) continue;
		V.push_back(i);
	}
	if(N==4 || K<=N) return _P("-1\n");
	_P("%d %d ",A,C);
	FOR(i,V.size()) _P("%d ",V[i]);
	_P("%d %d\n",D,B);
	_P("%d %d ",C,A);
	FOR(i,V.size()) _P("%d ",V[i]);
	_P("%d %d\n",B,D);
	
}

まとめ

本番はこれより少しややこしいコードを書いてたけど、まぁ通ってよかった。