9,10,13,14,16,18六个点RE
如果把
if(!_hash.find(v))q.push(v),_hash.push(v);
这句话删了就不会RE,也就是说是哈希的锅吗
#include <bits/stdc++.h>
using namespace std;
template <typename T>inline void read_10(T& t){
t=0; register char ch=getchar();
while(!('0'<=ch&&ch<='9'))ch=getchar();
while(('0'<=ch&&ch<='9')){t=t*10+ch-'0';ch=getchar();}
}
template <typename T>inline void read_2(T& t){
t=0; register char ch=getchar();
while(!('0'<=ch&&ch<='1'))ch=getchar();
while(('0'<=ch&&ch<='1')){t=t*2+ch-'0';ch=getchar();}
}
template <typename T,typename... Args> inline void read_10(T& t, Args&... args){read_10(t);read_10(args...);}
template <typename T,typename... Args> inline void read_2(T& t, Args&... args){read_2(t);read_2(args...);}
typedef long long ll;
const int K=1e6+5,NK=5e6+5,INF=1000033;
ll n,k,Poi[2],fl[2],del[K];
struct HASH{
struct edge{
int Next;
ll To;
}e[NK];
int head[INF+10];
int htot;
void push(ll v){
ll u=v%INF;
e[++htot].To=v;
e[htot].Next=head[u];
head[u]=htot;
}
bool find(ll v){
ll u=v%INF;
for(int i=head[u];i;i=e[i].Next)if(e[i].To==v)return 1;
return 0;
}
HASH(){
htot=0;
memset(head,0,sizeof(0));
}
}_hash;
queue<ll>q;
void bfs(int sta){
while(!q.empty())q.pop();
q.push(Poi[sta]);
_hash.push(Poi[sta]);
for(int i=1;i<=k;++i)_hash.push(del[i]);
while(!q.empty()){
if(++fl[sta]>n*k)return ;
ll u=q.front();
q.pop();
for(int i=0;i<n;++i){
ll v=u^(1ll<<i);
if(v==Poi[sta^1]){
puts("TAK");
exit(0);
}
if(!_hash.find(v))q.push(v),_hash.push(v);
}
}
puts("NIE");
exit(0);
}
int main(){
read_10(n,k);
read_2(Poi[0],Poi[1]);
for(int i=1;i<=k;++i)read_2(del[i]);
bfs(0);
_hash=HASH();
bfs(1);
puts("TAK");
return 0;
}