Submission #1168066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168066		hynmj	Walk (POI13_spa)	C++20	12 / 100	148 ms	15572 KiB

spa

//~~~~~~~~~~~~~MJ®™~~~~~~~~~~~~~
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#define rep1(n) for(ll i=0; i<(ll)(n); ++i)
#define rep2(i,n) for(ll i=0; i<(ll)(n); ++i)
#define rep3(i,a,b) for(ll i=(ll)(a); i<(ll)(b); ++i)
#define rep4(i,a,b,c) for(ll i=(ll)(a); i<(ll)(b); i+=(c))
#define cut4(a,b,c,d,e,...) e
#define rep(...) cut4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define per1(n) for(ll i=((ll)n)-1; i>=0; --i)
#define per2(i,n) for(ll i=((ll)n)-1; i>=0; --i)
#define per3(i,a,b) for(ll i=((ll)a)-1; i>=(ll)(b); --i)
#define per4(i,a,b,c) for(ll i=((ll)a)-1; i>=(ll)(b); i-=(c))
#define per(...) cut4(__VA_ARGS__,per4,per3,per2,per1)(__VA_ARGS__)
#define ll long long
#define ln cout<<endl
#define int long long
#define vv vector<vi>
#define vp vector<pi>
#define append push_back
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
#define vi vector<int>
#define ret(x) {cout<<x;return;}
#define ui map<int,int>
#define pi pair<int,int>
#define ff first
#define ss second
using namespace std;
const int INF = 1e18, MOD = 1e9+7, N = 9e6+7;
int binary_to_int(string s) {int n = 0; for (int i = 0; i < s.size(); i++) {n = n * 2 + s[i] - '0';} return n;}
// ul graph[N];
bool vis[N];
bool having[N];
vi path;
int st,en;
int n;
// void print()
// {
//     for (int i:path)
//     {
//         cout << i << " ";
//     }
//     ln;
// }
// void dfs(int node ,int p)
// {
//     vis[node]=1;
//     // path.append(node);
//     for (int j= n-1; j>=0; j--)
//     {
//         int i = 1<<j ^ node;
//         if (!having[i] and !vis[i])
//         {
//             dfs(i,node);
//         }         
//     }
//     // path.pop_back();

// }

void bfs(int node, int p)
{
    queue<int> q;
    q.push(node);
    vis[node]=1;
    while (!q.empty())
    {
        int node = q.front();
        q.pop();
        for (int j= n-1; j>=0; j--)
        {
            int i = 1<<j ^ node;
            if (!having[i] and !vis[i])
            {
                vis[i]=1;
                q.push(i);
            }         
        }
    }
}

void solve()
{
    int  k, m, ans = 0;
    string e, f;
    cin >> n >> k >> e >> f;
    st = binary_to_int(e);
    en = binary_to_int(f);
    vi a(k);
    rep(k)
    {
    	cin >> e;
        a[i]=binary_to_int(e);
        having [a[i]]=1;
    }
    
    bfs(st,-1);
    if (vis[en])
    {
        cout <<"TAK";
    }
    else
    {
        cout <<"NIE";
    }

    







     // cout << ans;
    // cout << a.size();
    // for (auto i: a){cout << i << " ";}
}
signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL); cout.tie(NULL);
    int ans=1;
    //cout<<setprecision(1000);
    // cin>>ans;
    rep(ans){
        // cout << "Case #" << i+1 << ": ";
        solve();ln;}}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 12
• Subtask 3: 0 / 12
• Subtask 4: 0 / 12
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13