oj.uz

Submission #316610

# Submission time Handle Problem Language Result Execution time Memory
316610 2020-10-26T22:58:08 Z thecodingwizard Walk (POI13_spa) C++11
12 / 100
 5000 ms 154996 KB 
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

int n, k; 
gp_hash_table<ll, null_type> dead({},{},{},{},{1<<20});

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) {
    gp_hash_table<ll, null_type> vis({},{},{},{},{1<<23});

    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.find(v) != vis.end() || dead.find(v) != dead.end()) 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();
    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 178 ms 148212 KB Output is correct
2 Correct 97 ms 148088 KB Output is correct
3 Correct 175 ms 148088 KB Output is correct
4 Correct 179 ms 148088 KB Output is correct
5 Correct 100 ms 148108 KB Output is correct
6 Correct 11 ms 16768 KB Output is correct
7 Correct 174 ms 148172 KB Output is correct
8 Correct 175 ms 148088 KB Output is correct
9 Correct 174 ms 148088 KB Output is correct
10 Correct 103 ms 148088 KB Output is correct
11 Correct 169 ms 148088 KB Output is correct

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 148216 KB Output is correct
2 Correct 257 ms 148728 KB Output is correct
3 Correct 4551 ms 154236 KB Output is correct
4 Correct 1416 ms 154996 KB Output is correct
5 Correct 1310 ms 154872 KB Output is correct
6 Execution timed out 5065 ms 21112 KB Time limit exceeded

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 175 ms 148116 KB Output is correct
2 Correct 2735 ms 149112 KB Output is correct
3 Execution timed out 5046 ms 149296 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 148088 KB Output is correct
2 Correct 103 ms 148092 KB Output is correct
3 Execution timed out 5078 ms 148732 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 256 ms 148088 KB Output is correct
2 Execution timed out 5068 ms 148828 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 148088 KB Output is correct
2 Execution timed out 5073 ms 149004 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 148088 KB Output is correct
2 Execution timed out 5017 ms 152056 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 273 ms 148088 KB Output is correct
2 Correct 447 ms 148216 KB Output is correct
3 Execution timed out 5075 ms 150452 KB Time limit exceeded
4 Halted 0 ms 0 KB -