oj.uz

Submission #316602

# Submission time Handle Problem Language Result Execution time Memory
316602 2020-10-26T22:30:31 Z thecodingwizard Walk (POI13_spa) C++11
24 / 100
 5000 ms 211788 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int n, k; 
set<ll> dead;

ll read() {
    ll num = 0;
    for (int i = n-1; i >= 0; i--) {
        char c; cin >> c;
        if (c == '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) {
    set<ll> vis;
    queue<ll> q; q.push(a); vis.insert(a);
    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;
            vis.insert(v);
            if ((int)vis.size() == ct || v == b) return true;
            q.push(v);
        }
    }
    return false;
}

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

    cin >> n >> k;

    ll a, b; a = read(), b = read();
    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
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 6 ms 512 KB Output is correct
4 Correct 60 ms 1144 KB Output is correct
5 Correct 27 ms 1152 KB Output is correct
6 Incorrect 0 ms 384 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 465 ms 12408 KB Output is correct
2 Correct 1050 ms 14072 KB Output is correct
3 Execution timed out 5072 ms 82484 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 118 ms 8056 KB Output is correct
3 Correct 277 ms 8184 KB Output is correct
4 Correct 57 ms 2552 KB Output is correct
5 Correct 26 ms 2680 KB Output is correct
6 Correct 2 ms 384 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 120 ms 5752 KB Output is correct
4 Correct 465 ms 15352 KB Output is correct
5 Correct 190 ms 15608 KB Output is correct

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 197 ms 6392 KB Output is correct
2 Execution timed out 5061 ms 211788 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 5112 KB Output is correct
2 Correct 1234 ms 70408 KB Output is correct
3 Correct 3125 ms 70556 KB Output is correct
4 Execution timed out 5094 ms 192996 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 346 ms 9976 KB Output is correct
2 Execution timed out 5022 ms 111356 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 341 ms 9776 KB Output is correct
2 Correct 185 ms 4344 KB Output is correct
3 Execution timed out 5080 ms 93188 KB Time limit exceeded
4 Halted 0 ms 0 KB -