Submission #1168269

#TimeUsernameProblemLanguageResultExecution timeMemory
1168269Faisal_SaqibWalk (POI13_spa)C++17
0 / 100
165 ms12196 KiB
#include <bitset> #include <iostream> #include <unordered_map> #include <map> #include <set> #include <queue> using namespace std; #define ll long long int n,k; char c; ll asp=0; // 10000000040 // 2e9 = 2000000000 // my pc limit = 8589884992 bitset<16000000000> ban; map<ll,ll> par; // unordered_map<ll,ll> par; ll read() { asp=0; for(int i=0;i<n;i++) { cin>>c; asp<<=1; asp+=c-'0'; } return asp; } ll pw2[70]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k; pw2[0]=1; for(int i=1;i<=n;i++) pw2[i]=2ll*pw2[i-1]; ll st=read(),ed=read(); set<ll> vis; for(int i=0;i<k;i++) { ll c=read(); vis.insert(c); } if(st==ed) { cout<<"TAK"<<endl; return 0; } // lets do a double sided bfs // better time complexity queue<ll>pq; ban[st]=1; pq.push(st); ban[ed]=1; pq.push(ed); par[st]=par[ed]=-1; while(pq.size()) { ll x=pq.front(); pq.pop(); // cout<<"At "<<x<<endl; for(int bi=0;bi<n;bi++) { ll y=x^pw2[bi]; if(vis.find(y)!=vis.end())continue; bool qp=ban[y]; if(par[x]!=y and qp) { // cout<<"At "<<x<<" going to "<<y<<endl; cout<<"TAK"<<endl; return 0; } if(!qp) { par[y]=x; ban[y]=1; pq.push(y); } } } cout<<"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...