Submission #70048027

---

Source Code Expand

#include <bits/stdc++.h>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;

void calc(){
  int N, M, K; cin >> N >> M >> K;
  string S; cin >> S;
  vector<vector<int>> G(N);
  for(int i=0; i<M; i++){
    int u,v; cin >> u >> v;
    u--; v--;
    G[u].push_back(v);
  }

  //「残り d 手で現在頂点 v にいるとき、最終的に Alice が勝てるか」
  vector<bool> cur(N), nxt(N);
  
  //後ろから・・・「残り手数が 0 のとき、頂点 v にいれば Alice が勝つか」
  for(int v=0; v<N; v++) cur[v]=(S[v]=='A'); 

  for(int d=1; d<=2*K; d++){
    bool bob = (d%2==1);
    // Bobターン
    // すべての遷移先で勝てないと負け
    if(bob){
      for(int v=0; v<N; v++){
        bool ok=true;
        for(int u: G[v]){
          if(!cur[u]) { ok=false; break; }
        }
        nxt[v] = ok;
      }
    // Aliceターン 
    // どれか1つでも勝てる遷移先があれば勝ち
    }else{
       for(int v=0; v<N; v++){
        bool ok=false;
        for(int u: G[v]){
          if(cur[u]) { ok=true; break; }
        }
        nxt[v] = ok;
      }
    }
    cur.swap(nxt);
  }
  cout << (cur[0] ? "Alice" : "Bob") << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);

  int T; cin >> T;
  while(T--) calc();
  return 0;
}

Submission Info

Judge Result