oj.uz

Submission #316613

# Submission time Handle Problem Language Result Execution time Memory
316613 2020-10-26T23:05:09 Z thecodingwizard Walk (POI13_spa) C++11
100 / 100
 2795 ms 57468 KB 
#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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 13 ms 1024 KB Output is correct
5 Correct 7 ms 1024 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 110 ms 9532 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 10556 KB Output is correct
2 Correct 386 ms 12952 KB Output is correct
3 Correct 2795 ms 51324 KB Output is correct
4 Correct 1537 ms 50284 KB Output is correct
5 Correct 1598 ms 50244 KB Output is correct
6 Correct 48 ms 5788 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 945 ms 46588 KB Output is correct
3 Correct 1847 ms 46876 KB Output is correct
4 Correct 1813 ms 46712 KB Output is correct
5 Correct 896 ms 46584 KB Output is correct
6 Correct 1655 ms 52040 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1762 ms 51824 KB Output is correct
4 Correct 1793 ms 51964 KB Output is correct
5 Correct 909 ms 47740 KB Output is correct

Subtask #5
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 5272 KB Output is correct
2 Correct 1266 ms 51840 KB Output is correct
3 Correct 2192 ms 56492 KB Output is correct
4 Correct 1868 ms 51252 KB Output is correct
5 Correct 31 ms 4100 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 4544 KB Output is correct
2 Correct 923 ms 48664 KB Output is correct
3 Correct 1760 ms 52008 KB Output is correct
4 Correct 1969 ms 50068 KB Output is correct
5 Correct 1029 ms 53248 KB Output is correct

Subtask #7
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 8892 KB Output is correct
2 Correct 1491 ms 53216 KB Output is correct
3 Correct 2567 ms 57468 KB Output is correct
4 Correct 2377 ms 52860 KB Output is correct
5 Correct 71 ms 7708 KB Output is correct

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 8640 KB Output is correct
2 Correct 65 ms 4388 KB Output is correct
3 Correct 2187 ms 48808 KB Output is correct
4 Correct 91 ms 7320 KB Output is correct
5 Correct 1171 ms 52072 KB Output is correct