C++(clang++11) 解法, 执行用时: 377ms, 内存消耗: 2580K, 提交时间: 2021-01-13 16:01:34

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+200,M=17;
int a[N],n,s,d[1<<M];
bool vis[1<<M];
int main()
{
    scanf("%d%d",&n,&s);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]),vis[a[i]]=1;
    int B=(1<<17)-1;
    memset(d,-1,sizeof d);
	d[a[s]]=0;
	queue<int>q;
	q.push(a[s]);
	while(!q.empty())
	{
	    int u=q.front();q.pop();
		int v=B^u;
		for(int w=v;w;w=(w-1)&v)
	    {
		    if(vis[w]&&d[w]==-1){
		    	d[w]=d[u]+1;q.push(w);
			}
		}	
		if(vis[0]&&d[0]==-1){
			d[0]=d[u]+1;q.push(0);
		}
	}  
	for(int i=1;i<=n;i++)
	{
		if(d[a[i]])printf("%d ",d[a[i]]);
		else if(i==s)printf("0 ");
		else if(a[i]==0)printf("1 ");
		else printf("2 ");
	}  
}