QOJ.ac

QOJ

Time Limit: 2 s Memory Limit: 256 MB Total points: 100
[+11]
Statistics

Alice 和 Bob 又打算玩游戏了。

有一个点数为 n 的有向无环图(点从 1 开始编号),每个点要么是黑点,要么是白点。图中可能有重边,每个点的出边是有序的。

有一段 DFS 程序,其伪代码如下:

定义过程 dfs(u)if u 是白点
        按顺序遍历 u 的所有出边 (u,v)
            读取一个布尔值 g
            if g
                dfs(v)
    else
        按顺序遍历 u 的所有出边 (u,v) 
            dfs(v)

读取一个整数 r
dfs(r)

这段程序还有一个特殊性质:程序会在每次 dfs 过程调用开始前自动暂停

Alice 和 Bob 启动了 k 个这样的程序,并给所有程序分别输入了一个点的编号作为 r(不同程序输入的 r 可能不同)。现在,这些程序都在读取 r 之后,调用 dfs(r) 之前暂停。

然后游戏开始。由 Alice 先手,双方轮流进行以下操作:

  • 选择一个尚未结束执行的程序,将其从暂停中恢复。继续执行该程序,直到它再次暂停或结束。在这个过程中,该程序每次读取 g,当前玩家都可以选择读取结果是 true 还是 false

每个程序都会在有限次暂停后结束,最终所有程序均会结束执行。如果轮到一名玩家操作时所有程序均已结束执行,该玩家输掉游戏,另一名玩家获胜。

双方都会采取最优策略。谁能获胜?

输入格式

第一行,一个正整数 n,表示图的点数。

第二行,n 个整数 c1,c2,,cn,表示每个点的颜色。cu=0 表示 u 是黑点,cu=1 表示 u 是白点。

接下来 n 行描述图中的边,其中第 i 行有一个非负整数 mimi 个正整数 ei,1,ei,2,,ei,mi,分别表示 i 的出边数量和各出边的终点。为了方便,保证对于所有 1in1jmi,有 ei,j>i;即 1,2,,n 是该图的一个拓扑序。

接下来一行,一个正整数 k,表示程序数量。

最后一行,k 个正整数 r1,r2,,rk,分别表示游戏开始前各程序的输入。

输出格式

一行,一个字符串,表示获胜者。如果 Alice 获胜,输出 Alice;如果 Bob 获胜,输出 Bob

样例一

input

4
1 0 1 0
1 2
2 4 3
1 4
0
1
2

output

Alice

explanation

该图有 4 个点。

  • 1:白色,一条出边,终点为 2
  • 2:黑色,两条出边,终点分别为 43
  • 3:白色,一条出边,终点为 4
  • 4:黑色,没有出边。

只有一个程序,其初始点为点 2。以下为双方采取最优策略时该程序的执行过程:

  1. 输入初始点 r=2 并暂停执行。游戏开始,接下来轮到 Alice。因为只有一个程序,双方总是只能选择这个程序。Alice 选择继续执行该程序。
  2. dfs(2)
    1. 暂停执行。轮到 Bob。Bob 选择继续执行该程序。
    2. dfs(4)
      1. 过程返回
    3. 暂停执行。轮到 Alice。Alice 选择继续执行该程序。
    4. dfs(3)
      1. 读取一个布尔值 g。Alice 选择 false
      2. 过程返回
    5. 过程返回
  3. 结束执行。轮到 Bob。

轮到 Bob 时所有程序均已结束执行,Bob 输掉游戏,Alice 获胜。

在该样例中,点 1 存在与否实际上对游戏过程没有影响。

另外,如果 Alice 在 dfs(3) 中选择 true,那么接下来 dfs(3) 会调用 dfs(4),并在调用前多暂停一次。这会导致结束执行时轮到 Alice,获胜者会变成 Bob。由于双方均采取最优策略,这样的事情不会发生。

样例二

input

5
1 1 0 0 1
2 3 5
2 3 5
2 5 4
0
0
2
1 2

output

Bob

explanation

两个程序的初始点分别为 12,而点 12 的颜色、出边完全一致,只有编号不同。

Bob 可以采取以下策略:当 Alice 选择执行某个程序后,Bob 选择执行另一个程序并给出相同的输入。容易证明这是 Bob 的必胜策略。

样例三

input

10
0 0 0 0 1 1 1 1 0 1
1 2
2 3 4
0
3 5 8 10
1 6
1 7
0
1 9
0
0
1
1

output

Bob

数据范围

对于所有数据:

  • 1n2×105
  • ci{0,1}(对于所有 1in
  • 0mi4×105(对于所有 1in
  • ni=1mi4×105
  • i<ei,jn(对于所有 1in1jmi
  • 1k2×105
  • 1rin(对于所有 1ik
子任务 分值 特殊限制
1 5 ci=0(对于所有 1in
2 15 k=1r1=1
3 15 n10ni=1mi10k10
4 20 ci=1(对于所有 1in);对于每个点 u,只有至多一条边的终点为 u;对于所有 1ik,图中不存在终点为 ri 的边
5 20 ci=1(对于所有 1in
6 25 没有额外的约束条件

时间限制:2s

空间限制:256MB