Submission #316613

#	Time	Username	Problem	Language	Result	Execution time	Memory
316613		thecodingwizard	Walk (POI13_spa)	C++11	100 / 100	2795 ms	57468 KiB

spa

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n, k; 
unordered_set<ll> dead;

ll read() {
    string s; cin >> s;
    ll num = 0;
    for (int i = n-1; i >= 0; i--) {
        if (s[n-1-i] == '1') {
            num |= (1LL << i);
        }
    }
    return num;
}

// return true if a can reach b or if a can reach at least ct nodes
bool solve(ll a, ll b, int ct) {
    unordered_set<ll> vis;

    queue<ll> q; q.push(a);
    vis.insert(a);
    --ct;

    while (!q.empty()) {
        ll u = q.front(); q.pop();
        for (int i = 0; i < n; i++) {
            ll v = u ^ (1LL << i);
            if (vis.count(v) || dead.count(v)) continue;
            --ct;
            if (ct == 0 || v == b) return true;
            vis.insert(v);
            q.push(v);
        }
    }
    return false;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> n >> k;

    ll a, b; a = read(), b = read();
    if (a == b) {
        cout << "TAK\n";
        return 0;
    }
    for (int i = 0; i < k; i++) {
        ll x = read();
        dead.insert(x);
    }

    cout << (solve(a, b, 1000000) && solve(b, a, 1000000) ? "TAK" : "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