Submission #1168352

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168352		MuhammadSaram	Walk (POI13_spa)	C++20	100 / 100	4912 ms	59016 KiB

spa

#include <bits/stdc++.h>

using namespace std;

#define int long long

set<int> se;

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 x=i^(1LL<<p);
				if (se.find(x)==se.end() && vis.find(x)==vis.end())
					nxt.push_back(x),vis.insert(x);
			}
		}
		if (nxt.empty())
			return vis.find(y)!=vis.end();
		else if(nxt.size()>k)
			return 1;
		else
			cur=nxt;
	}
}

signed main()
{
	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 (bfs(x,y,n,k) && bfs(y,x,n,k))
		cout<<"TAK"<<endl;
	else
		cout<<"NIE"<<endl;
	
	return 0;
}

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