Submission #1143199

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143199		alexnicu	Walk (POI13_spa)	C++17	12 / 100	242 ms	162320 KiB

spa

#include <iostream>
#include <string>
#include <vector>
#include <queue>

using namespace std;

bool existing_numbers[(1<<23) + 5];

int string_to_number( string s ) {
    int ans = 0, pow = 0;
    for ( int i = s.size() - 1; i >= 0; i-- ) {
        if ( s[i] == '1' ) {
            ans = ans + ( 1 << pow );
        }
        pow++;
    }
    return ans;
}
int finish;
bool ans = false;
int n;
void dfs( int node ) {
    existing_numbers[node] = true;
    if (existing_numbers[finish] == true ) {
        ans = true;
        return;
    }
    for(int i = 0; i < n; i++ )
        if(existing_numbers[node^(1<<i)] == false)
            dfs((node^(1<<i)));
    return;
}

int main() {
    int k;
    cin >> n >> k;
    string a, b;
    cin >> a >> b;
    int start;
    start = string_to_number(a);
    finish = string_to_number(b);
    string s;
    for ( int i = 1; i <= k; i++ ) {
        cin >> s;
        existing_numbers[string_to_number(s)] = true;
    }
    if ( start == finish ) {
        cout << "TAK";
        return 0;
    }
    existing_numbers[start] = true;
    dfs(start);
    if ( ans == true )
        cout << "TAK";
    else
        cout << "NIE";
    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