Submission #1143339

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143339		adimiclaus15	Walk (POI13_spa)	C++20	12 / 100	341 ms	11320 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;int n,nr2=0;
void BFS(){
    while(!q.empty()){
        int nr=q.front();q.pop();
        for(int i=0;i<n;i++){
            int nr1=nr;
            if((nr&(1<<i))!=0){nr1-=(1<<i);}
            else{nr1+=(1<<i);}
            if(f[nr1]==0&&ajuns[nr1]==0){
                q.push(nr1);ajuns[nr1]=1;
            }
        }
        if(ajuns[nr2]==1){break;}
    }
}
int main()
{
    int 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);ajuns[nr1]=1;
    if(nr1==nr2){
        cout<<"TAK"<<'\n';return 0;
    }
    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