# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
316617 |
2020-10-26T23:10:11 Z |
thecodingwizard |
Walk (POI13_spa) |
C++11 |
|
4824 ms |
262148 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;
stack<ll> q; q.push(a);
vis.insert(a);
--ct;
while (!q.empty()) {
ll u = q.top(); 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 |
14 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 |
0 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 |
9436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
208 ms |
10656 KB |
Output is correct |
2 |
Correct |
464 ms |
12604 KB |
Output is correct |
3 |
Correct |
4073 ms |
185968 KB |
Output is correct |
4 |
Correct |
4611 ms |
96736 KB |
Output is correct |
5 |
Correct |
4510 ms |
96300 KB |
Output is correct |
6 |
Correct |
48 ms |
4508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
52 ms |
8472 KB |
Output is correct |
3 |
Correct |
95 ms |
8556 KB |
Output is correct |
4 |
Correct |
18 ms |
2468 KB |
Output is correct |
5 |
Correct |
9 ms |
2444 KB |
Output is correct |
6 |
Correct |
1 ms |
384 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 |
53 ms |
5696 KB |
Output is correct |
4 |
Correct |
270 ms |
16748 KB |
Output is correct |
5 |
Correct |
147 ms |
16700 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
103 ms |
5276 KB |
Output is correct |
2 |
Runtime error |
2717 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 |
83 ms |
4508 KB |
Output is correct |
2 |
Correct |
894 ms |
68092 KB |
Output is correct |
3 |
Correct |
1709 ms |
74780 KB |
Output is correct |
4 |
Correct |
4824 ms |
179036 KB |
Output is correct |
5 |
Correct |
2677 ms |
171288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
151 ms |
8764 KB |
Output is correct |
2 |
Runtime error |
2536 ms |
262148 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 |
173 ms |
8572 KB |
Output is correct |
2 |
Correct |
68 ms |
4252 KB |
Output is correct |
3 |
Correct |
2011 ms |
87052 KB |
Output is correct |
4 |
Correct |
4422 ms |
178916 KB |
Output is correct |
5 |
Correct |
2448 ms |
178708 KB |
Output is correct |