oj.uz

Submission #316630

# Submission time Handle Problem Language Result Execution time Memory
316630 2020-10-26T23:22:05 Z thecodingwizard Walk (POI13_spa) C++11
74 / 100
 4554 ms 262144 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;
}

ll s[4000001];
unordered_set<ll> vis;
// return true if a can reach b or if a can reach at least ct nodes
bool solve(ll a, ll b, int ct) {
    vis.clear();
    int idx = 0;
    s[idx] = a;
    vis.insert(a);
    --ct;

    while (idx >= 0) {
        ll u = s[idx--];
        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);
            s[++idx] = v;
            assert(idx <= 4000000);
        }
    }
    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, n*k+1) && solve(b, a, n*k+1) ? "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 1 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 0 ms 384 KB Output is correct
7 Correct 0 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 121 ms 9488 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 214 ms 10556 KB Output is correct
2 Correct 456 ms 12864 KB Output is correct
3 Correct 3603 ms 184472 KB Output is correct
4 Correct 4554 ms 97068 KB Output is correct
5 Correct 4494 ms 96840 KB Output is correct
6 Correct 50 ms 4636 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 48 ms 8536 KB Output is correct
3 Correct 77 ms 8476 KB Output is correct
4 Correct 14 ms 2444 KB Output is correct
5 Correct 9 ms 2444 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 46 ms 5276 KB Output is correct
4 Correct 207 ms 16572 KB Output is correct
5 Correct 120 ms 16572 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 5300 KB Output is correct
2 Runtime error 2739 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 4508 KB Output is correct
2 Correct 764 ms 67712 KB Output is correct
3 Correct 1279 ms 67708 KB Output is correct
4 Correct 4135 ms 170144 KB Output is correct
5 Correct 2277 ms 170316 KB Output is correct

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 8768 KB Output is correct
2 Runtime error 2753 ms 262144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #8
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 161 ms 8636 KB Output is correct
2 Correct 71 ms 4252 KB Output is correct
3 Correct 1680 ms 86320 KB Output is correct
4 Correct 3907 ms 177712 KB Output is correct
5 Correct 2133 ms 177580 KB Output is correct