RE求助
查看原帖
RE求助
668765
atom_yan楼主2023/10/8 20:33

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;
}
2023/10/8 20:33
加载中...