제출 #316623

#제출 시각아이디문제언어결과실행 시간메모리
316623thecodingwizard새로운 문제 (POI13_spa)C++11
74 / 100
4780 ms262148 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; } ll s[5000001]; // 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; int idx = 0; s[idx] = a; vis.insert(a); --ct; while (idx >= 0) { ll u = s[idx--]; 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); s[++idx] = 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...