제출 #1143162

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1143162		alexnicu	Walk (POI13_spa)	C++20	12 / 100	503 ms	327680 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;
}

vector<int> search_neighbors(int x, int n) {
    vector<int> ans;
    int cx = x;
    for ( int i = n - 1; i >= 0; i-- ) {
       if ( x >= (1 << i) ){
        ans.push_back(cx - (1 << i));
        x -= (1 << i);
       }
       else
        ans.push_back(cx + (1 << i));
    }
    return ans;
}
int finish;
bool ans = false;
int n;
void dfs( int node ) {
    if (node == finish ) {
        ans = true;
        return ;
    }
    vector<int> ans = search_neighbors(node, n);
    for ( auto nr: ans ) {
        if (existing_numbers[nr] == false ) {
            existing_numbers[nr] = true;
            dfs(nr);
        }
    }
    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;
    }
    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