Submission #1168334

#TimeUsernameProblemLanguageResultExecution timeMemory
1168334Ghulam_JunaidWalk (POI13_spa)C++20
25 / 100
5098 ms327680 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N = 61, K = 1e6 + 10; int n, k, ite; ll X[2]; bool done; set<ll> blocked, seen; int dist(ll u, ll v){ return __builtin_popcount(u ^ v); } void bfs(ll v, ll f){ set<pair<int, ll>> st; st.insert({dist(v, f), v}); seen.insert(v); while (!st.empty()){ ite++; auto [d, v] = *st.begin(); st.erase(st.begin()); if (v == f){ done = 1; break; } for (int i = 0; i < n; i ++){ ll u = v ^ (1ll << i); if (blocked.find(u) != blocked.end()) continue; if (seen.find(u) != seen.end()) continue; if (dist(u, f) > dist(v, f) and ite >= n * k) continue; st.insert({dist(u, f), u}); seen.insert(u); } } } 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 ++){ ll cur = 0; for (int j = 0; j < n; j ++){ char c; cin >> c; cur = cur * 2 + (c - '0'); } blocked.insert(cur); } if (X[0] == X[1]){ cout << "TAK" << endl; return 0; } bfs(X[0], X[1]); if (done){ 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...