Nebius Welcome Round : E. Routing

こっちの方がすんなりだった。
https://codeforces.com/contest/1804/problem/E

問題

N点M辺の連結無向グラフが与えられる。
各点uに対し、問い合わせ先A(u)が定められている場合、u→vのパスが存在するか以下のようにチェックする。

• vがuの隣接点なら、u→vが求めるパスである。
• vがuの隣接点でない場合、A(u)→vとなるパスがあるか判定し、存在するならu→A(u)→vが求めるパスとなる。そのようなパスがなければ、パスが存在できない。

任意の2頂点間でパスの存在判定ができるAの組み合わせがあるか判定し、あるなら一例を示せ。

解法

どの頂点からでもvにパスが貼れ、かつvからどの頂点にも移動できるようなvを探そう。
dp(mask,v) := maskに示す頂点集合のうち、v以外の頂点uのA(u)を定めたとき、条件を満たすか。満たすなら復元用の情報を入れておく。
上記値をbitdpで順次埋めて行き、最後に復元する。

int N,M;
int E[20];

int dp[1<<20][20];
int to[20];

void hoge(int mask,int from,int to,vector<int>& ret) {
	ret.push_back(to);
	if(from==to) return;
	int i;
	FOR(i,N) if((mask&(1<<i))&&(dp[mask^(1<<to)][from]&(1<<i))&&E[i]&(1<<to)) {
		hoge(mask^(1<<to),from,i,ret);
		return;
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		x--,y--;
		E[x]|=1<<y;
		E[y]|=1<<x;
	}
	FOR(i,N) if(E[i]==(1<<N)-1) {
		cout<<"Yes"<<endl;
		FOR(j,N) {
			if(i!=j) cout<<i+1<<" ";
			else cout<<(j?(j-1):j+1)<<" ";
		}
		cout<<endl;
		return;
	}
	FOR(i,N) dp[1<<i][i]=1<<i;
	int mask;
	int ok=0;
	FOR(mask,1<<20) {
		int e=0;
		FOR(i,N) if(mask&(1<<i)) e|=E[i];
		if(e==(1<<N)-1) {
			FOR(i,N) {
				FOR(j,N) if((dp[mask][i]&(1<<j))&&E[j]&(1<<i)) {
					vector<int> ret;
					hoge(mask,i,j,ret);
					reverse(ALL(ret));
					FOR(i,ret.size()) to[ret[i]]=ret[(i+1)%ret.size()]+1;
					FOR(i,N) if(to[i]==0) {
						FOR(j,N) if(to[j]&&E[i]&(1<<j)) {
							to[i]=j+1;
							break;
						}
					}
					cout<<"Yes"<<endl;
					FOR(i,N) cout<<to[i]<<" ";
					cout<<endl;
					return;
					
				}
			}
		}
		
		FOR(i,N) FOR(j,N) if(dp[mask][i]&(1<<j)) {
			FOR(k,N) if((mask&(1<<k))==0&&E[j]&(1<<k)) {
				dp[mask|(1<<k)][i]|=1<<k;
			}
		}
		
	}
	cout<<"No"<<endl;
}

まとめ

なぜこれよりDに手間取っているのか…。