제출 #316616

#제출 시각아이디문제언어결과실행 시간메모리
316616thecodingwizard새로운 문제 (POI13_spa)C++11
49 / 100
5090 ms262144 KiB
#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 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...