제출 #1168171

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168171		MuhammadSaram	Walk (POI13_spa)	C++20	37 / 100	5096 ms	112032 KiB

spa

#include <bits/stdc++.h>

using namespace std;

#define int long long

unordered_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 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()>3*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: 0 / 12
• Subtask 3: 12 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 13 / 13