Submission #1168206

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168206		AbdullahIshfaq	Walk (POI13_spa)	C++20	100 / 100	4143 ms	244936 KiB

spa

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MOD 1000000007
ll dec_to_bin(string s){
	ll res = 0;
	for(auto i : s){
		res = res * 2 + (i - '0');
	}
	return res;
}
void solve(){
	ll n, k, c = (1 << 22) - 1;
	cin >> n >> k;
	string s, t;
	cin >> s >> t;
	unordered_set<ll> vis, dang;
	ll st = dec_to_bin(s), en = dec_to_bin(t);
	for(int i = 0; i < k ;i ++){
		cin >> s;
		ll z = dec_to_bin(s);
		dang.insert(z);
	}
	bool check1 = 0, check2 = 0;
	queue<ll> q, q2;
	q.push(st);
	while(!q.empty()){
		ll u = q.front();
		q.pop();
		for(auto i = 0; i < n; i ++){
			ll v = u ^ (1ll << i);
			if(vis.find(v) != vis.end() or dang.find(v) != dang.end()){
				continue;
			}
			c--;
			if(v == en or st == en or !c){
				check1 = 1;
				break;
			}
			vis.insert(v);
			q.push(v);
		}
		if(check1){
			break;
		}
	}
	c = (1 << 22) - 1;
	vis.clear();
	q2.push(en);
	while(!q2.empty()){
		ll u = q2.front();
		q2.pop();
		for(auto i = 0; i < n; i ++){
			ll v = u ^ (1ll << i);
			if(vis.find(v) != vis.end() or dang.find(v) != dang.end()){
				continue;
			}
			c--;
			if(v == st or st == en or !c){
				check2 = 1;
				break;
			}
			vis.insert(v);
			q2.push(v);
		}
		if(check2){
			break;
		}
	}
	if(check1 and check2){
		cout << "TAK" << '\n';
	}
	else{
		cout << "NIE" << '\n';
	}
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int tests = 1;
	// cin >> tests;
	for(int i = 1; i <= tests; i ++)
		solve();
}

• 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