Submission #1143323

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143323		adimiclaus15	Walk (POI13_spa)	C++20	12 / 100	1006 ms	55284 KiB

spa

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>

using namespace std;
const int NMAX = 4194310;
bool f[NMAX+5],ajuns[NMAX+5];
queue<int>q;queue<string>qq;int nr2=0;
void BFS(){
    while(!q.empty()){
        int nr=q.front();q.pop();
        string s=qq.front(),s1;qq.pop();
        for(int i=0;i<s.size();i++){
            s1=s;int nr1=nr;
            if(s[i]=='1'){s1[i]='0';nr1-=(1<<i);}
            else{s1[i]='1';nr1+=(1<<i);}
            if(f[nr1]==0&&ajuns[nr1]==0){
                q.push(nr1);qq.push(s1);ajuns[nr1]=1;
            }
        }
        if(ajuns[nr2]==1){break;}
    }
}
int main()
{
    int n,k;cin>>n>>k;string a,b,s;cin>>a>>b;
    int nr1=0;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    for(int i=0;i<a.size();i++){
        if(a[i]=='1'){nr1=nr1+(1<<i);}
    }
    for(int i=0;i<b.size();i++){
        if(b[i]=='1'){nr2=nr2+(1<<i);}
    }
    for(int i=1;i<=k;i++){
        cin>>s;int nr=0;
        reverse(s.begin(),s.end());
        for(int j=0;j<s.size();j++){
            if(s[j]=='1'){nr=nr+(1<<j);}
        }
        f[nr]=1;
    }
    q.push(nr1);qq.push(a);ajuns[nr1]=1;
    BFS();
    if(ajuns[nr2]==0){
        cout<<"NIE"<<'\n';
    }
    else{
        cout<<"TAK"<<'\n';
    }
    return 0;
}

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