Submission #1168341

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168341		UmairAhmadMirza	Walk (POI13_spa)	C++20	100 / 100	1081 ms	36248 KiB

spa

#include <bits/stdc++.h>
using namespace std;

#define int long long
int const N=61;
int const mod=1e9+7;

int n,k;
int pw[N];
set<int> rem;

bool check(int sr,int tg){
	set<int> vis;
	for(int i:rem)
		vis.insert(i);
	vector<int> st;
	st.push_back(sr);
	vis.insert(sr);
	while(st.size()>0){
		int nd=st.back();
		st.pop_back();
		if(nd==tg)
			return 1;
		for(int i=0;i<n;i++){
			int nw=(nd^(pw[i]));
			if(vis.find(nw)==vis.end() && rem.find(nw)==rem.end()){
				vis.insert(nw);
				st.push_back(nw);
				if(nw==tg || vis.size()>3*k)
					return 1;
			}
		}
	}
	return 0;
}


signed main(){
	cin>>n>>k;
	pw[0]=1;
	for (int i = 1; i < n; ++i)
		pw[i]=(pw[i-1]*2);
	string xx,yy;
	cin>>xx>>yy;
	int x=0,y=0;
	for(int i=0;i<n;i++){
		if(xx[i]=='1')
			x+=pw[i];
		if(yy[i]=='1')
			y+=pw[i];
	}
	for (int i = 0; i < k; ++i)
	{
		string c;
		cin>>c;
		int a=0;
		for (int i = 0; i < n; ++i)
			a+=pw[i]*(c[i]=='1');
		rem.insert(a);
	}
	if(check(x,y) && check(y,x))
		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