Codeforces #663 Div2 E. Pairs of Pairs

この回残念ながら本番中に解き切れてないなぁ。
https://codeforces.com/contest/1391/problem/E

問題

N点M辺からなる連結無向グラフが与えられる。
以下のいずれかを構築せよ。

• ceil(N/2)頂点以上からなるパス
• ceil(N/2)頂点以上からなる頂点対の集合
  • ただし、どの頂点対を2つ選んだ場合も、計4点からなる頂点対6ペアのうち、辺があるのは2ペア以下であること

解法

DFS順に頂点を探索し、根からの距離を求めよう。
その際、距離がceil(N/2)以上の点があるなら、明らかに条件を満たすパスが作れる。
そうでない場合、同じ距離同士のものをペアにしていこう。
距離の最長値がceil(N/2)以下なので、同じ距離の点が奇数個で余りが出たとしても、それはceil(N/2)個未満である。

int T;
int N,M;
vector<int> E[505050];

int id[505050];
int D[505050];
int P[505050];
int cand[505050];
int vis[505050];

void dfs(int cur,int pre,int id,int d) {
	if(vis[cur]) return;
	vis[cur]=1;
	P[cur]=pre;
	D[cur]=d;
	if(D[cand[id]]<d) cand[id]=cur;
	FORR(e,E[cur]) if(vis[e]==0) dfs(e,cur,id,d+1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>M;
		FOR(i,N) {
			E[i].clear();
			D[i]=0;
			cand[i]=0;
			vis[i]=0;
		}
		FOR(i,M) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		vector<pair<int,int>> V;
		V.push_back({0,0});
		V.push_back({0,0});
		vis[0]=1;
		FORR(e,E[0]) {
			dfs(e,0,e,1);
			V.push_back({D[cand[e]],cand[e]});
		}
		sort(ALL(V));
		reverse(ALL(V));
		vector<int> R,R2;
		int cur=V[0].second;
		while(cur!=0) {
			R.push_back(cur);
			cur=P[cur];
		}
		R.push_back(0);
		cur=V[1].second;
		while(cur!=0) {
			R2.push_back(cur);
			cur=P[cur];
		}
		reverse(ALL(R2));
		FORR(r,R2) R.push_back(r);
		if(2*R.size()>=N) {
			cout<<"PATH"<<endl;
			cout<<R.size()<<endl;
			FORR(r,R) cout<<r+1<<" ";
			cout<<endl;
		}
		else {
			FOR(i,N) vis[i]=-1;
			R.clear();
			FOR(i,N) {
				if(vis[D[i]]==-1) {
					vis[D[i]]=i;
				}
				else {
					R.push_back(i);
					R.push_back(vis[D[i]]);
					vis[D[i]]=-1;
				}
			}
			
			cout<<"PAIRING"<<endl;
			cout<<R.size()/2<<endl;
			FOR(i,R.size()/2) {
				cout<<R[i*2]+1<<" "<<R[i*2+1]+1<<endl;
			}
			
		}
	}
}

まとめ

Codeforces、2種類のうちのどちらかを作れって問題時々出るよね。