Submission #1168347

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168347		MuhammadSaram	새로운 문제 (POI13_spa)	C++20	12 / 100	5099 ms	159048 KiB

spa

#include <bits/stdc++.h>

using namespace std;

#define int long long

unordered_set<int> se;
int tr=4e6;

bool bfs(int x,int y,int n,int k)
{
	vector<int> cur={x};
	set<int> vis={x};
	while (1)
	{
		
		vector<int> nxt;
		for (int i:cur)
		{
			for (int p=0;p<n;p++)
			{
				int z=i^(1<<p);
				if (se.find(z)==se.end() && vis.find(z)==vis.end())
					nxt.push_back(z),vis.insert(z);
			}
		}
		if (nxt.empty())
			return vis.find(y)!=vis.end();
		else if(nxt.size()>k*100)
			return 1;
		else
			cur=nxt;
	}
}

bool bfs1(int x,int y,int n)
{
	vector<int> cur={x};
	set<int> vis={x};
	while (1)
	{
		
		vector<int> nxt;
		for (int i:cur)
		{
			for (int p=0;p<n;p++)
			{
				int z=i^(1<<p);
				if (se.find(z)==se.end() && vis.find(z)==vis.end())
					nxt.push_back(z),vis.insert(z);
				if (z==y)
					return 1;
			}
		}
		if (nxt.empty())
			return 0;
		cur=nxt;
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	
	int n,k;
	cin>>n>>k;
	string s,s1;
	cin>>s>>s1;
	int x=0,y=0;
	for (char c:s)
		x=x*2+c-'0';
	for (char c:s1)
		y=y*2+c-'0';
	for (int i=0;i<k;i++)
	{
		char c;
		int val=0;
		for (int j=0;j<n;j++)
		{
			cin>>c;
			val=val*2+c-'0';
		}
		se.insert(val);
	}
	if (n>22)
	{
		if (bfs(x,y,n,k) && bfs(y,x,n,k))
			cout<<"TAK"<<endl;
		else
			cout<<"NIE"<<endl;
	}
	else
		exit(-1);
	
	return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 12
• Subtask 3: 12 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13