#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);
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();
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;
}
# |
결과 |
실행 시간 |
메모리 |
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 |
0 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 |
111 ms |
9536 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
191 ms |
10684 KB |
Output is correct |
2 |
Correct |
378 ms |
12860 KB |
Output is correct |
3 |
Execution timed out |
5098 ms |
148804 KB |
Time limit exceeded |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
70 ms |
8348 KB |
Output is correct |
3 |
Correct |
131 ms |
8796 KB |
Output is correct |
4 |
Correct |
26 ms |
2596 KB |
Output is correct |
5 |
Correct |
14 ms |
2444 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
512 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
3 |
Correct |
73 ms |
5568 KB |
Output is correct |
4 |
Correct |
350 ms |
16748 KB |
Output is correct |
5 |
Correct |
181 ms |
16576 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
93 ms |
5276 KB |
Output is correct |
2 |
Runtime error |
4654 ms |
262148 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
85 ms |
4556 KB |
Output is correct |
2 |
Correct |
1258 ms |
67580 KB |
Output is correct |
3 |
Correct |
2459 ms |
72928 KB |
Output is correct |
4 |
Execution timed out |
5109 ms |
169748 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
162 ms |
8960 KB |
Output is correct |
2 |
Execution timed out |
5063 ms |
173792 KB |
Time limit exceeded |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
170 ms |
8700 KB |
Output is correct |
2 |
Correct |
72 ms |
4380 KB |
Output is correct |
3 |
Correct |
4093 ms |
83600 KB |
Output is correct |
4 |
Correct |
91 ms |
7324 KB |
Output is correct |
5 |
Correct |
4972 ms |
170508 KB |
Output is correct |