# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
316616 |
2020-10-26T23:09:25 Z |
thecodingwizard |
Walk (POI13_spa) |
C++11 |
|
5000 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;
}
// 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, n*k+1) && solve(b, a, n*k+1) ? "TAK" : "NIE") << endl;
return 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 |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
384 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
110 ms |
9408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
204 ms |
10580 KB |
Output is correct |
2 |
Correct |
381 ms |
12732 KB |
Output is correct |
3 |
Execution timed out |
5090 ms |
150716 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
69 ms |
8344 KB |
Output is correct |
3 |
Correct |
136 ms |
8844 KB |
Output is correct |
4 |
Correct |
26 ms |
2580 KB |
Output is correct |
5 |
Correct |
14 ms |
2444 KB |
Output is correct |
6 |
Correct |
1 ms |
512 KB |
Output is correct |
# |
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 |
80 ms |
5680 KB |
Output is correct |
4 |
Correct |
335 ms |
16624 KB |
Output is correct |
5 |
Correct |
178 ms |
16704 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
95 ms |
5272 KB |
Output is correct |
2 |
Runtime error |
4633 ms |
262144 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
89 ms |
4504 KB |
Output is correct |
2 |
Correct |
1269 ms |
67572 KB |
Output is correct |
3 |
Correct |
2409 ms |
73124 KB |
Output is correct |
4 |
Execution timed out |
5083 ms |
169748 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
163 ms |
8892 KB |
Output is correct |
2 |
Execution timed out |
5063 ms |
174400 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
165 ms |
8640 KB |
Output is correct |
2 |
Correct |
70 ms |
4380 KB |
Output is correct |
3 |
Correct |
4110 ms |
83268 KB |
Output is correct |
4 |
Correct |
96 ms |
7324 KB |
Output is correct |
5 |
Correct |
4956 ms |
170436 KB |
Output is correct |