an awesome question of basic graph traversal (786A), C++ (gcc)

an awesome question of basic graph traversal (786A)

#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define pb push_back

const int win = 1;
const int los = 0;
const int act = 3;
const int drw = 2;

int dp[2][7001], cnt[2][7001], k1, k2, n;

vector<int> a, b;

void solve(){
    queue<pii> q;
    q.push(mp(1, 0));
    dp[0][1] = 0;
    q.push(mp(1, 1));
    dp[1][1] = 0;
    
    while(!q.empty()){
        int from = q.front().first, chance = q.front().second;
        q.pop();
        int res = dp[chance][from];
        
        const vector<int>& v = (chance == 0)? b : a;
        for(auto i : v){
            int cur = (from - i + n) % n;
            if(cur == 0) cur = n;
            if(dp[chance^1][cur] != -1) continue;
            
            if(res == los){
                //cout << from << " " << chance << " " << cur << " win" << endl;
                dp[chance^1][cur] = win;
                q.push(mp(cur, chance^1));
            }else{
                cnt[chance^1][cur]++;
                if(cnt[chance^1][cur] == v.size()){
                    //cout << from << " " << chance << " " << cur << " lose" << endl;
                    dp[chance^1][cur] = los;
                    q.push(mp(cur, chance^1));
                }
            }
        }
    }
    
    for(int j = 1; j <= n; j++) for(int i = 0; i < 2; i++) if(dp[i][j] == -1) dp[i][j] = 2;
}

int main(){
    ios_base :: sync_with_stdio(0);
    cin.tie(0);
    
    memset(dp, -1, sizeof(dp));
    memset(cnt, 0, sizeof(cnt));
    
    cin >> n;
    cin >> k1;
    a.resize(k1);
    for(int j = 0; j < k1; j++) cin >> a[j];
    cin >> k2;
    b.resize(k2);
    for(int j = 0; j < k2; j++) cin >> b[j];
    
    solve();
    //cout << foo(0, 2) << endl;
    for(int j = 2; j <= n; j++){
        int x = dp[0][j];
        if(x == win) cout << "Win" << " ";
        else if(x == los) cout << "Lose" << " ";
        else cout << "Loop" << " ";
        //memset(dp, -1, sizeof(dp));
    }
    cout << endl;
    for(int j = 2; j <= n; j++){
        int x = dp[1][j];
        if(x == win) cout << "Win" << " ";
        else if(x == los) cout << "Lose" << " ";
        else cout << "Loop" << " ";
    }
    return 0;
}


run \| edit \| history \| help	0

λ

                                      .NET NoSQL database for rapid development