Submission #316632

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
316632	2020-10-26T23:30:31 Z	thecodingwizard	Walk (POI13_spa)	C++11	36 / 100	2362 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[3000001];
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 <= 3000000);
        }
    }
    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	8 ms	1024 KB	Output is correct
6	Correct	1 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	0 ms	384 KB	Output is correct
10	Correct	0 ms	384 KB	Output is correct
11	Correct	113 ms	9404 KB	Output is correct

Subtask #2
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	217 ms	10684 KB	Output is correct
2	Correct	458 ms	12732 KB	Output is correct
3	Runtime error	2362 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
4	Halted	0 ms	0 KB	-

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	8476 KB	Output is correct
3	Correct	95 ms	8408 KB	Output is correct
4	Correct	19 ms	2444 KB	Output is correct
5	Correct	10 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	50 ms	5148 KB	Output is correct
4	Correct	225 ms	16700 KB	Output is correct
5	Correct	169 ms	16572 KB	Output is correct

Subtask #5
0 / 13.0

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

Subtask #6
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	99 ms	4508 KB	Output is correct
2	Correct	844 ms	67572 KB	Output is correct
3	Correct	1327 ms	67560 KB	Output is correct
4	Runtime error	2075 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Halted	0 ms	0 KB	-

Subtask #7
0 / 13.0

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

Subtask #8
0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	164 ms	8640 KB	Output is correct
2	Correct	73 ms	4380 KB	Output is correct
3	Correct	1671 ms	86300 KB	Output is correct
4	Runtime error	2040 ms	262144 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
5	Halted	0 ms	0 KB	-

Submission #316632

Compilation message