Submission #1168208

#TimeUsernameProblemLanguageResultExecution timeMemory
1168208Ghulam_JunaidWalk (POI13_spa)C++20
12 / 100
4430 ms327680 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 61, K = 1e6 + 10; int n, k, seen2; int X[2]; unordered_map<int, bool> blocked; unordered_map<int, int> seen; void bfs(){ queue<int> q[2], nq[2]; q[0].push(X[0]); seen[X[0]] = 1; q[1].push(X[1]); seen[X[1]] = 2; while (!q[0].empty() and !q[1].empty()){ while (!q[0].empty()){ int v = q[0].front(); q[0].pop(); for (int i = 0; i < n; i ++){ int nv = (1 << i) ^ v; if ((blocked[nv]) or seen[nv] == 1) continue; if (seen[nv] == 2) seen2 = 1; seen[nv] = 1; nq[0].push(nv); } } while (!q[1].empty()){ int v = q[1].front(); q[1].pop(); for (int i = 0; i < n; i ++){ int nv = (1 << i) ^ v; if ((blocked[nv]) or seen[nv] == 2) continue; if (seen[nv] == 1) seen2 = 1; seen[nv] = 2; nq[1].push(nv); } } if (nq[0].size() >= k and nq[1].size() >= k) seen2 = 1; if (seen2) break; for (int i = 0; i < 2; i ++) while (!nq[i].empty()) q[i].push(nq[i].front()), nq[i].pop(); } } int main(){ cin >> n >> k; for (int i = 0; i < 2; i ++){ for (int j = 0; j < n; j ++){ char c; cin >> c; X[i] = X[i] * 2 + (c - '0'); } } if (X[0] > X[1]) swap(X[0], X[1]); for (int i = 0; i < k; i ++){ int cur = 0; for (int j = 0; j < n; j ++){ char c; cin >> c; cur = cur * 2 + (c - '0'); } blocked[cur] = 1; } if (X[0] == X[1]){ cout << "TAK" << endl; return 0; } bfs(); if (seen2){ cout << "TAK" << endl; return 0; } cout << "NIE" << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...